| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 18 | 11 | 9 | 75.000% |
In a police investigation, n suspects were identified and now it’s up to the witnesses to try to find the perpetrator. The height of every suspect i was measured, but due to the unreliability of measurement, it is known only that their height is a real number from the interval from li to ri (inclusive). At most one of the suspects is the perpetrator, and it could be the case that none of them are.
A signle lineup consists of choosing two positive integers a and b (1 ≤ a ≤ b ≤ n), then taking the suspects a, a + 1, ..., b to a separate room so that the witnesses could try to identify the perpetrator. As the witnesses could be confused if two of the suspects have the same height, a lineup is allowed only if it is possible to guarantee that no two suspects will have the same height. During a lineup, the witnesses will always be able to identify the perpetrator if he is among the chosen suspects, or they will be able to tell that he is not among them.
The lead investigator is now interested in answering questions of the following form: “If I were certain that the label of the perpetrator could only be between p and q (p ≤ q), what is the minimum number of lineups needed in the worst case so that the witnesses are able to find the perpetrator, or report that he is not among the suspects?” Help the lead investigator answer q of such questions.
The first line contains a positive integer n, the number of suspects.
The following n lines contain two positive integers li and ri (1 ≤ li ≤ ri ≤ 109) which represent the possible height range of the suspect with label i.
The next line contains a positive integer q, the number of questions.
The following q lines contain two positive integers pi and qi (1 ≤ pi ≤ qi ≤ n) which determine a question.
In q lines print the answers to the corresponding questions: the minimum required number of lineups.
In every subtask, it holds that 1 ≤ n, q ≤ 200 000.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | q = 1, p1 = 1, q1 = n |
| 2 | 10 | 1 ≤ n ≤ 5000, 1 ≤ q ≤ 5000 |
| 3 | 20 | 1 ≤ n ≤ 5000, 1 ≤ q ≤ 200 000 |
| 4 | 20 | 1 ≤ n ≤ 200 000, 1 ≤ q ≤ 100 |
| 5 | 50 | No additional constraints. |
2 1 1 1 1 3 1 1 2 2 1 2
1 1 2
3 1 1 2 2 3 3 3 1 1 2 3 1 3
1 1 1
5 1 3 3 3 4 6 2 3 1 1 3 1 4 3 5 1 5
3 1 3
Clarification of the third example:
For the first and the third question, it is sufficient to have three lineups: one consists of the suspect 1, one consists of the suspects 2 and 3, and one consists of the suspects 4 and 5.
For the second question, it is sufficient to have one lineup which consists of the suspects 3, 4 and 5.