C - Third Largest Number
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
3 以上の整数 N と長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
k=3,4,\ldots,N それぞれに対し以下の問題を解いてください：
- A_1,A_2,\ldots,A_k を降順に並べたとき、前から 3 番目にくる値を求めてください。
制約
- 3\le N\le 5\times 10^5
- 1\le A_i\le 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
N-2 行出力せよ。
i 行目 (1\le i\le N-2) には k=i+2 とした時の答えを出力せよ。
入力例 1
5 1 2 1 2 3
出力例 1
1 1 2
- k=3 のとき：A_1,A_2,A_3 を降順に並べると 2,1,1 となります。前から 3 番目に来る値は 1 なので、1 行目には 1 を出力してください。
- k=4 のとき：A_1,A_2,A_3,A_4 を降順に並べると 2,2,1,1 となります。前から 3 番目に来る値は 1 なので、2 行目には 1 を出力してください。
- k=5 のとき：A_1,A_2,A_3,A_4,A_5 を降順に並べると 3,2,2,1,1 となります。前から 3 番目に来る値は 2 なので、3 行目には 2 を出力してください。
入力例 2
10 1 1 1 3 2 5 4 3 6 5
出力例 2
1 1 1 2 3 3 4 5
入力例 3
10 11 9 1 3 17 19 10 19 17 3
出力例 3
1 3 9 11 11 17 17 17
Score : 300 points
Problem Statement
You are given an integer N not less than 3 and a length-N sequence of positive integers A=(A_1,A_2,\ldots,A_N).
For each k=3,4,\ldots,N, solve the following problem:
- When A_1,A_2,\ldots,A_k are sorted in descending order, find the third value from the front.
Constraints
- 3\le N\le 5\times 10^5
- 1\le A_i\le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Output N-2 lines.
The i-th line (1\le i\le N-2) should contain the answer for k=i+2.
Sample Input 1
5 1 2 1 2 3
Sample Output 1
1 1 2
- For k=3: sorting A_1,A_2,A_3 in descending order gives 2,1,1. The third value from the front is 1, so output 1 on the first line.
- For k=4: sorting A_1,A_2,A_3,A_4 in descending order gives 2,2,1,1. The third value from the front is 1, so output 1 on the second line.
- For k=5: sorting A_1,A_2,A_3,A_4,A_5 in descending order gives 3,2,2,1,1. The third value from the front is 2, so output 2 on the third line.
Sample Input 2
10 1 1 1 3 2 5 4 3 6 5
Sample Output 2
1 1 1 2 3 3 4 5
Sample Input 3
10 11 9 1 3 17 19 10 19 17 3
Sample Output 3
1 3 9 11 11 17 17 17