Dizalo
레이팅 미적용의견: 0
In one city there is a tall skyscraper with \(n\) floors. There are \(n\) people waiting
for an elevator on the ground floor. The \(i-th\) person wants to go to the floor \(a@@RISE_MATH_BLOCK_0@@i\)
were not \(in\) the elevator, how many exits would there \(be\) then?
Mirko is interested in an answer before Slavko’s first question and after every question. Note that for each
question, all the people from previous questions are also not considered to be in the elevator.
Mirko started solving the problem but soon realized that even for him, this would not be quite easy. Help
him solve this problem!
Note: The elevator will always move from the first floor to the \(n-th\) floor and stop at every floor on which
someone wants to exit.
Subtask 1 (16 points): n, \(q \le 100\)
Subtask 2 (19 points): n, \(q \le 1\,000\)
Subtask 3 (29 points): \(q = 0\)
Subtask 4 (46 points): No additional constraints.
The first line contains two n\(on-ne\)gative integers \(n\) and \(q\) (\(0 \le q < n \le 10^{5}\)), the number of peop\(le/fl\)oors
and the number of questions.
The second line contains \(n\) integers \(a@@RISE_MATH_BLOCK_0@@i \le n\), a\(i\)̸ = \(a@@RISE_MATH_BLOCK_1@@i\) is the floor on which
the \(i-th\) person wants to exit the elevator. The sequence (\(a@@RISE_MATH_BLOCK_2@@i\) (\(1 \le x@@RISE_MATH_BLOCK_3@@j\) for each \(i\)̸ = \(j\)), Slavko’s questions.
In one line, print \(q + 1\) numbers, where the \(i-th\) is the number of exists after \(i - 1\) questions.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 16점 | n, \(q \le 100\) |
2 | 19점 | n, \(q \le 1\,000\) |
3 | 29점 | \(q = 0\) |
4 | 46점 | No additional constraints. |
5 2
3 4 1 2 5
3 29 6 47 0
4 5 2 1 6 3 7133 2
3 1 2
1 25 2 1Clarification of the first example:
The illustration shows the exits from the elevator before the first query.
The elevator is on the first floor, and the person at position 3 wants to
exit. But, for them to exit, persons at positions 1 and 2 must exit first,
and they return to the elevator at the same positions.
After that, on the second floor, the person at position 4 wants to exit.
Again, persons at positions 1 and 2 must exit first, and they return to
the elevator at the same positions.
After that, on the third floor, the person at position 1 exits the elevator,
without anyone else having to exit the elevator.
After that, on the fourth floor, the person at position 2 exits the elevator,
without anyone else having to exit the elevator.
And finally, on the fifth floor, the person at position 5 exits the elevator.
In total, there were 3 + 3 + 1 + 1 + 1 = 9 exits from the elevator.
평가 및 의견
Dizalo
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Dizalo