Zatopljenje
레이팅 미적용의견: 0
It’s winter, it has never been colder, and Mr. Malnar is looking at his photos from
his last cruise on the Adriatic and recalls unforgettable moments. The TV is on in
the background, broadcasting news about the latest proposals for measures to slow
down sea level rise. Looking at his photos of the coast, Mr. Malnar asks himself
what the photos would have looked like if sea level had risen a certain amount.
There are so many pictures, and even more questions, so Mr. Malnar asks for your
help.
We imagine the coast as a sequence of \(n\) numbers \(h\)1, h2, . . . , h\(n\), where the \(i-th\) number represents relief
height at the \(i-th\) point. Mr. Malnar has \(q\) queries, where the \(i-th\) query is as following: How many islands
would there \(be\) between the \(l@@RISE_MATH_BLOCK_0@@i-th\) point \(if\) the sea level rose \(by\) \(x@@RISE_MATH_BLOCK_1@@i\) is strictly greater than the sea level. A
maximal interval is one that cannot be extended in either direction while keeping the mentioned condition
true. Initially, the sea level is at 0 meters.
Subtask 1 (10 points): n, \(q \le 2 \cdot 10^{3}\)
Subtask 2 (20 points): \(l@@RISE_MATH_BLOCK_0@@1 \ge h\)2 ≥· · · ≥\(h@@RISE_MATH_BLOCK_1@@p \le h@@RISE_MATH_BLOCK_2@@n\)
Subtask 4 (60 points): No additional constraints.
The first line contains integers \(n\) and \(q\) (\(1 \le n\), \(q \le 2 \cdot 10^{5}\)), the length of the sequence and the number of
queries.
The second line contains \(n\) integers \(h\)1, h2, . . . , h\(n\) (\(0 \le h@@RISE_MATH_BLOCK_0@@i\), \(r@@RISE_MATH_BLOCK_1@@i\) (\(1 \le l@@RISE_MATH_BLOCK_2@@i \le n\), \(0 \le x\)\(i \le 10^{9}\)) that
describe the \(i-th\) query.
In the \(i-th\) of the \(q\) lines print the answer to the \(i-th\) query. Each of the queries is independent of the
others.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | n, \(q \le 2 \cdot 10^{3}\) |
2 | 20점 | \(l\)\(i = 1\), r\(i = n\) for all \(i = 1\), 2, . . . , q |
3 | 20점 | There exists an integer \(p\) (\(1 \le p \le n\)) such that the following holds: \(h@@RISE_MATH_BLOCK_0@@p\) i \(h@@RISE_MATH_BLOCK_1@@p+1\) ≤· · · ≤\(h\)\(n\) |
4 | 60점 | No additional constraints. |
6 3
2 4 2 3 4 1
2 5 2
3 5 3
3 4 42
1
010 3
5 0 3 4 2 0 1 6 3 5
3 9 1
1 10 3
1 10 22
4
3Clarification of the first example:
The first query is shown in the left image in the task description, islands correspond to intervals [2, 2] and
[4, 5]. In the second query island corresponds to interval [5, 5]. In the third query there are no islands
because everything is under water.
Clarification of the second example:
In the first query islands correspond to intervals [3, 5] and [8, 9]. In the second query (shown in the right
image in the task description) islands correspond to intervals [1, 1], [4, 4], [8, 8] and [10, 10], while in the
third query islands correspond to intervals [1, 1], [3, 4] and [8, 10].
평가 및 의견
Zatopljenje
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Zatopljenje