308846: CF1583G. Omkar and Time Travel
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Omkar and Time Travel
题意翻译
给定 $n$ 个传送点,第 $i$ 个从 $b_i$ 传送回 $a_i$($1\leq a_i<b_i \leq 2n$ 且 $a_i, b_i$ 全部互不相同),从 $0$ 开始往右走,若走到一个 $b_i$ 且之前没有标记过 $i$ ,则标记它,返回 $a_i$ ,并消除所有 $a_j>a_i$ 的标记的 $j$。给定一个集合,求最早的一次满足集合内的所有传送点都被标记的传送次数。题目描述
El Psy Kongroo. Omkar is watching Steins;Gate. In Steins;Gate, Okabe Rintarou needs to complete $ n $ tasks ( $ 1 \leq n \leq 2 \cdot 10^5 $ ). Unfortunately, he doesn't know when he needs to complete the tasks. Initially, the time is $ 0 $ . Time travel will now happen according to the following rules: - For each $ k = 1, 2, \ldots, n $ , Okabe will realize at time $ b_k $ that he was supposed to complete the $ k $ -th task at time $ a_k $ ( $ a_k < b_k $ ). - When he realizes this, if $ k $ -th task was already completed at time $ a_k $ , Okabe keeps the usual flow of time. Otherwise, he time travels to time $ a_k $ then immediately completes the task. - If Okabe time travels to time $ a_k $ , all tasks completed after this time will become incomplete again. That is, for every $ j $ , if $ a_j>a_k $ , the $ j $ -th task will become incomplete, if it was complete (if it was incomplete, nothing will change). - Okabe has bad memory, so he can time travel to time $ a_k $ only immediately after getting to time $ b_k $ and learning that he was supposed to complete the $ k $ -th task at time $ a_k $ . That is, even if Okabe already had to perform $ k $ -th task before, he wouldn't remember it before stumbling on the info about this task at time $ b_k $ again. Please refer to the notes for an example of time travelling. There is a certain set $ s $ of tasks such that the first moment that all of the tasks in $ s $ are simultaneously completed (regardless of whether any other tasks are currently completed), a funny scene will take place. Omkar loves this scene and wants to know how many times Okabe will time travel before this scene takes place. Find this number modulo $ 10^9 + 7 $ . It can be proven that eventually all $ n $ tasks will be completed and so the answer always exists.输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the number of tasks that Okabe needs to complete. $ n $ lines follow. The $ k $ -th of these lines contain two integers $ a_k $ and $ b_k $ ( $ 1 \leq a_k < b_k \leq 2n $ ) — the time at which Okabe needs to complete the $ k $ -th task and the time that he realizes this respectively. All $ 2n $ of these times are distinct (so every time from $ 1 $ to $ 2n $ inclusive appears exactly once in the input). The next line contains a single integer $ t $ ( $ 1 \leq t \leq n $ ) — the size of the set $ s $ of tasks that lead to the funny scene. The last line contains $ t $ integers $ s_1, s_2, \ldots, s_t $ — ( $ 1 \leq s_k \leq n $ , the numbers $ s_1, s_2, \ldots, s_t $ are distinct) — the set $ s $ of tasks.
输出格式
Output a single integer — the number of times that Okabe time travels until all tasks in the set $ s $ are simultaneously completed, modulo $ 10^9 + 7 $ .
输入输出样例
输入样例 #1
2
1 4
2 3
2
1 2
输出样例 #1
3
输入样例 #2
2
1 4
2 3
1
1
输出样例 #2
2
输入样例 #3
1
1 2
1
1
输出样例 #3
1
输入样例 #4
6
10 12
3 7
4 6
2 9
5 8
1 11
3
2 4 6
输出样例 #4
17
输入样例 #5
16
31 32
3 26
17 19
4 24
1 28
15 21
12 16
18 29
20 23
7 8
11 14
9 22
6 30
5 10
25 27
2 13
6
3 8 2 5 12 11
输出样例 #5
138