651 . 區間完全覆蓋問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

83.3% (5/6)

Tags

apcsc apcsc-timecomplexity

Description

給定一個數列 $a$，由從 $1$ 到 $N$ 編號的 $N$ 個整數組成。

讓我們將數組的 $k$- 區間完全數 定義為 為出現在所有長度為 $k$ 的子陣列 (子陣列在這裡是連續的，恰好包含 k 個元素) 的交集中，最小的那個數。
如果沒有數字滿足在所有長度為 $k$ 的子陣列中都有該數字，則此數列的 $k$- 區間完全數 為 $-1$。

假設數列為 1 2 3 4 5, $k = 4$，長度為 $k$ 的子陣列有 1 2 3 4 和 2 3 4 5 其中 $2$ 是在所有子陣列的交集中，最小的數字

現在小 U 希望找出 $k$ 從 $1$ 到 $N$ 的每一個 $k$- 區間完全數。

Input Format

輸入第一行有一個正整數 $N$，代表數列 $X$ 的長度。第二行有 $N$ 個數字以空白隔開，為數列 $X$ 的第 $i$ 個數。

  • $1 \le N \le 10^ 6$
  • $1 \le X_i \le N$

Output Format

輸出 $N$ 個數字並以空白隔開，依序代表 $k$ 從 $1$ 到 $N$ 的 $k$-區間完全數

Sample Input 1

5
1 2 3 4 5

Sample Output 1

-1 -1 3 2 1

Sample Input 2

5
4 4 4 4 2

Sample Output 2

-1 4 4 4 2

Sample Input 3

6
1 3 1 5 3 1

Sample Output 3

-1 -1 1 1 1 1

Hints

Problem Source

CodeForces 1416 pA

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~19 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
Submit
Back to Top