Osumnjičeni
레이팅 미적용의견: 0
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 \(l@@RISE_MATH_BLOCK_0@@i\) (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 \le a \le b \le 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 \le 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.
Subtask 1 (10 points): \(q = 1\), \(p_{1} = 1\), \(q_{1} = n\)
Subtask 2 (10 points): \(1 \le n \le 5000\), \(1 \le q \le 5000\)
Subtask 3 (20 points): \(1 \le n \le 5000\), \(1 \le q \le 200\,000\)
Subtask 4 (20 points): \(1 \le n \le 200\,000\), \(1 \le q \le 100\)
Subtask 5 (50 points): No additional constraints.
The first line contains a positive integer \(n\), the number of suspects.
The following \(n\) lines contain two positive integers \(l@@RISE_MATH_BLOCK_0@@i\) (\(1 \le l@@RISE_MATH_BLOCK_1@@i \le 10^{9}\)) 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 \(p_{i}\) and \(q_{i}\) (\(1 \le p_{i} \le q_{i} \le n\)) which determine a question.
In \(q\) lines print the answers to the corresponding questions: the minimum required number of lineups.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(q = 1\), \(p_{1} = 1\), \(q_{1} = n\) |
2 | 10점 | \(1 \le n \le 5000\), \(1 \le q \le 5000\) |
3 | 20점 | \(1 \le n \le 5000\), \(1 \le q \le 200\,000\) |
4 | 20점 | \(1 \le n \le 200\,000\), \(1 \le q \le 100\) |
5 | 50점 | No additional constraints. |
2
1 1
1 1
3
1 1
2 2
1 21
1
23
1 1
2 2
3 3
3
1 1
2 3
1 31
1
15
1 3
3 3
4 6
2 3
1 1
3
1 4
3 5
1 53
1
3Clarification 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.
평가 및 의견
Osumnjičeni
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Osumnjičeni