TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

68.0% (17/25)

Submission's AC Ratio

23.0% (70/305)

Tags

Description

你有聽過提姆嗎?對,就是魔法少女的寵物。每個魔法少女都會養一些提姆來當寵物,有些提姆甚至可以用來打掃、搬運、或是騙取路人的同情心進而騙吃騙喝之類的...不,提姆是用來戰鬥的,擁有強大的提姆軍團是所有魔法少女的目標。

而傳說中拿過魔奧(IMO,International Magic Olympiad)金牌的魔法少女,小向,當然也有養很多的提姆。

提姆是需要訓練的,小向每天都會用一些任務訓練他的提姆們。
要知道提姆是有不同的個性的,有些比較電,喜歡獨自完成任務;有些喜歡團隊合作, 讓別的提姆來凱瑞他 ,由數個提姆一起完成任務。
小向每天都會分配一些任務,有些任務必須要一隻提姆完成,有些需要多隻。而小向很怕他出的任務太難或太多,導致提姆們很難過。

於是小向找到了你,天龍國立大學提姆研究所的研究員,現在給你一堆提姆,還有小向每天的任務,請你告訴小向那一天的任務提姆們可不可以完成,完成後他可能會送你一隻提姆感謝你。

Input Format

第1行有一個數字 T,代表有 T 組測試資料。
每組測試資料第1行有一個 N ,代表提姆的數量,
接著 N 行,第 i 行有兩個介於[1,N]之間的整數 Ai、Bi,代表第 i 隻提姆喜歡的組隊人數範圍。
接下來有一個整數 Q,代表小向的詢問筆數,
接下來 Q 行,每行第一個數字為 M ,代表這天有 M 個任務,緊接著有 M 個整數,代表每個任務需要的組隊人數。

21%,$ N \leq 100, Q \leq 100 $
13%,$ N \leq 100,000, Q = 1 $
43%,$ N \leq 100,000, Q \leq 100,000, S \leq 100,000 $
23%,$ N \leq 500,000, Q \leq 200,000, S \leq 200,000 $
其中S代表所有Q之中M的總和。

Output Format

對於每次詢問,輸出一行,包含一個整數0或1,如果那天的任務提姆們可以完成輸出1,否則輸出0。

Sample Input

1
4
1 2
2 3
2 3
2 4
2
2 1 3
2 1 1

Sample Output

1
0

Hints

對於範例輸入,N = 4,Q = 2,提姆1~4分別喜歡的範圍是[1,2][2,3][2,3][2,4]。

第1天小向給了兩個任務,各需要1和3個提姆,可以由1號提姆完成第一個,剩下3個提姆完成第二個。

第2天小向給了兩個任務,各需要1和1個提姆,因為只有一隻提姆可以組成單人隊伍,所以今天的任務提姆們沒有辦法完成。

Problem Source

IOI 2015 Day 1
Problem set / Description by 果茶

Subtasks

For Testdata: 0 ~ 0, Score: 21
For Testdata: 1 ~ 1, Score: 13
For Testdata: 2 ~ 2, Score: 43
For Testdata: 3 ~ 3, Score: 23
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 1048576 65536
1 3000 1048576 65536
2 18000 1048576 65536
3 54000 1048576 65536