ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#1946

[고등부] 2023 KOI 대비 모의고사 (5월 1주차)

기준
サブタスク
3秒 512MB

問題

즐거운 체육 시간이다. 

 

체육관에 학생들은 키 순서대로 줄을 서 있다. ​​

체육 선생님은 준비 운동을 위해 기준을 잡고 싶어한다. 

기준이 되는 학생은 ​중앙에 있는 학생이다.

만약 중앙이 되는 학생이 2명 있으면 그 중 키가 더 작은 학생이 기준이 된다. 2명의 키가 같다면 둘 중 아무나 기준이 된다.

 

체육관에 학생들이 들어오기 시작했다.

 

한번에 키가 v_i​인 학생이 a_i명 들어온다.

총 n번 들어올 때, 학생들이 들어올 때마다 기준이 되는 학생의 키를 구하라.


入力

첫 줄에 체육관에 학생들이 들어오는 횟수 n(1 ≤ n ≤ 200,000)이 주어진다.

다음 n줄에 걸쳐 들어오는 학생의 키 v_i​ 와 학생의 수 a_i​ 가 주어진다. (1 ≤ v_i, a_i​​ ≤ 10^9)


出力

n줄에 걸쳐 기준이 되는 학생의 키를 출력한다.


部分問題

番号 点数 条件
#116点

n, v_i ≤ 1000

#223点

a_i = 1

#327点

v_1​,v_2​< ... <v_n

#434点

추가 제약 조건 없음


例題 #1

3

2 1

3 1

1 1
2

2

2

例題 #2

4

17 2

23 5

11 4

9 5
17

23

17

11

例題 #3

3

10 20

100 5

1000 5
10

10

10
ログインしないとコードを書けません。