위태로운 쌓기

시간 제한4초메모리 제한1024 MB

요약

N개의 정사각형을 주어진 순서대로 떨어뜨릴 때, 각 단계 후 구조물의 최고 y 좌표를 구합니다.

난이도: 보통10점 중 5점
유형: 세그먼트 트리, 정렬
정답자: 아직 제출이 없습니다

문제

요즘 IT 업계에서 일자리를 구하기가 어렵다. 당신은 건설 회사에 취업했지만, 맡겨지는 일 중에는 엔지니어들이 중력이라는 걸 들어본 적이 있는지 의문이 드는 것도 있다. 이번 작업에서는 건설 프로젝트 모델을 평가해야 한다.

이 모델은 축에 평행한 정사각형들을 지면, 즉 직선 $y=0$ 을 향해 떨어뜨려 만들어진다. 각 정사각형에는 정해진 $x$ 좌표와 크기가 있다. 정사각형은 밑면이 지면이나 다른 정사각형에 닿을 때까지 아래로 내려간다. 정사각형이 한 번 착지하면 제자리에 단단히 고정되므로, 두 정사각형의 균형이 맞지 않아도 쓰러지지 않는다.

정사각형들과 떨어뜨릴 순서가 주어질 때, 정사각형을 하나씩 놓은 뒤 구조물이 도달하는 최대 $y$ 좌표를 구하라.

입력

첫째 줄에 정사각형의 개수를 나타내는 정수 $N$ ( $1 \le N \le 10^5$ )이 주어진다. 이어지는 $N$ 개의 줄은 떨어뜨릴 순서대로 정사각형을 설명한다. $i$ 번째 줄에는 두 정수 $x_i$ ( $0 \le x_i \le 10^9$ )와 $s_i$ ( $1 \le s_i \le 10^9$ )가 주어지며, 각각 정사각형 $i$ 의 왼쪽 가장자리 $x$ 좌표와 크기를 뜻한다.

출력

$N$ 개의 줄을 출력한다. $i$ 번째 줄에는 정사각형 $1,\dots,i$ 를 떨어뜨린 뒤 구조물이 도달한 가장 높은 $y$ 좌표를 출력한다.

예제4

예제 1
입력
```
3
0 1
0 2
0 3
```
예상 출력
```
1
3
6
```
예제 2
입력
```
5
0 1
0 10
9 1
0 10
9 10
```
예상 출력
```
1
11
12
22
32
```
예제 3
입력
```
3
0 1
1 1
2 1
```
예상 출력
```
1
1
1
```

예제 4

입력

예상 출력