30248번 - Airplanes 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
문제
A new airport has been opened in Bitlandia. It is considered to be the most advanced airport in the whole world. There is a short-distance teleportation system installed which allows the travellers to get in, get out or transfer to another plane in a blink of an eye. Moreover, this even allows the planes to not stop at the airport and the system can provide this service to a multiple planes at the same time.
However,the creators of the system have not accounted for the fact that the situation can become quite complicated if passengers have to transfer from one plane to another. Let’s say that passengers need to transfer from plane i to plane j. Since planes do not stop at the airport, the plane j cannot land (and take off again) earlier than plane i does.
If the plane i is late, then the plane j will have to wait for it before landing. This means that it can delay other flights as well in case travellers from plane j need to transfer.
In an effort to solve this problem, the government of Bitlandia has issued a law stating that all travellers from the same flight have the right to transfer to at most one other flight. Moreover, the mayor of Bitlandia has ordered to create a flight control system that would allow tracking when each plane will land (and take off again).
Create this flight control system. You will be provided with regular flight schedule and information about transfers of travellers between flights.
The system will have to answer two types of queries:
- Output the currently expected landing time of plane j.
- Accept notice that plane j will be additionally late z units of time.
입력
The first line of the input contains the number of planes N.
The second line the contains N integers 1 ≤ p1 ≤ p2 ≤ . . . ≤ pN ≤ 1 000 000 000. pi shows that according to regular schedule, the plane i has to land at the airport at the moment pi.
Further, there are N − 1 lines showing which planes the travellers are going to transfer to.
ith of these lines contains number yi (i < yi) meaning that there will be passengers wishing to transfer from plane i to plane yi.
The number of queries Q is given next. Each of the remaining Q lines contains one out of two possible queries:
- I j – output the currently expected landing time of plane j;
- P j z – the plane j will additionally be late z units of time.
출력
Output the currently expected landing time of the corresponding plane for each I query. Output the numbers on separate lines.
제한
- 2 ≤ N ≤ 200 000
- 1 ≤ Q ≤ 100 000
- Upon the execution of the program, the plane landing time time will not exceed 1 000 000 000.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | yi = i + 1, 2 ≤ N ≤ 1 000, 1 ≤ Q ≤ 1 000 |
| 2 | 6 | 2 ≤ N ≤ 1 000, 1 ≤ Q ≤ 1 000 |
| 3 | 40 | yi = i + 1 |
| 4 | 49 | No additional constraints |
예제 입력 1
4 2 4 5 7 2 3 4 11 I 4 P 4 2 I 4 P 1 3 I 1 I 2 I 3 P 2 1 I 1 I 2 I 3
예제 출력 1
7 9 5 5 5 5 6 6
According to the regular flight schedule, plane 4 has to land at the time moment 7:
However, a new notification is received that it is going to be late until the 9’th moment of time:
Then a notification is received about the delay of plane 1 – now it is expected to land at the 5’th moment of time. Because of the delay of this plane, the plane 2 will also have to be kept on air:
Notification: the plane 2 is going to be late by an additional 1 unit of time. Now it is going to land at the 6’th moment of time. Because of its delay, the plane 3 will also have to be delayed.
예제 입력 2
4 1 2 4 8 3 3 4 9 I 2 I 3 P 2 3 I 2 I 3 P 1 6 I 1 I 2 I 3
예제 출력 2
2 4 5 5 7 5 7
According to the primary flight schedule, the plane 2 has to land at the 2’nd moment of time and the plane 3 – at the 4’th moment of time.
Then a notification about the delay of the plane 2 is received:
Now the planes 2 and 3 will arrive at the 5’th moment of time.
Finally there arrives notification about the delay of plane 1. Therefore the plane 3 will be delayed (the arrival time of plane 2 does not change, because there are no passengers wishing to transfer from plane 1 to plane 2). Finally, a notification about the delay of the plane 1 is received. Because of its delay, the plane 3 will also have to be delayed. (note that arrival of the plane 2 does not change as there are no passengers wishing to transfer from the plane 1 to the plane 2).
출처
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2016/2017 > National Round (2) > 10-12 Classes ?번
채점 및 기타 정보
- 예제는 채점하지 않는다.