1443 . 康莊大道

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

wiwiho

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

17.6% (3/17)

Tags

ioicamp ioicamp-2026

Description

本題記憶體限制為 256MB，但是如果你使用超過 64MB (VSS)，你只能獲得 90% 的分數。

小奕從臺灣大學畢業以後，他很快就迎來了人生的康莊大道……那是一條他在夢裡夢到的道路。

他夢中的康莊大道是一條長度為 $N$ 公尺的直線道路，一開始這條道路什麼都沒有，接下來有 $M$ 個事件依序發生，在第 $i$ 個事件發生時，會有一顆石頭從天而降，掉落在道路上距離起點 $x_i$ 公尺的地方，這顆石頭的顏色是 $c_i$。如果有多顆石頭掉落在同一個位置，它們會好好地疊起來，不會滾到別的地方（夢境裡發生的事情通常都不太符合現實世界的物理），因此可能同一個位置會有很多顆石頭。

從夢中醒來後，小奕對於這個莫名其妙的夢摸不著頭緒，為了知道這個夢境的意義，他提出了 $Q$ 個問題，第 $i$ 個問題是「道路上距離起點 $[\ell_i,r_i]$ 公尺的區間內，最早是從第幾個事件之後開始，有 $k_i$ 種不同顏色的石頭呢？」

小奕起床後就先把他記憶中的 $M$ 個事件記錄下來了，但他趕著要去上班，請你幫他找出這 $Q$ 個問題的答案。

Input Format

輸入第一行有兩個整數 $N,M$，分別代表康莊大道的長度和事件的數量。

接下來有 $M$ 行，其中第 $i$ 行有兩個整數 $x_i,c_i$，代表第 $i$ 個事件是有一顆顏色 $c_i$ 的石頭掉落在道路上距離起點 $x_i$ 公尺處。

下一行有一個整數 $Q$，代表小奕有幾個問題。

接下來有 $Q$ 行，其中第 $i$ 行有三個整數 $\ell_i,r_i,k_i$，代表小奕想知道 $[\ell_i,r_i]$ 區間從什麼時候開始有 $k_i$ 種不同顏色的石頭。

  • $1 \leq N, M, Q \leq 3 \times 10^ 5$
  • $1 \leq x_i \leq N$
  • $1 \leq c_i \leq 3 \times 10^ 5$
  • $1 \leq \ell_i \leq r_i \leq N$
  • $1 \leq k_i \leq M$

Output Format

輸出 $Q$ 行，其中第 $i$ 行輸出一個整數 $t_i$，代表區間 $[\ell_i, r_i]$ 中，最早是從第 $t_i$ 個事件過後開始，有至少 $k_i$ 種不同顏色的石頭。如果區間 $[\ell_i, r_i]$ 中從來都沒有 $k_i$ 種不同顏色的石頭，輸出 -1。

Sample Input 1

8 10
3 1
5 2
2 3
5 1
8 4
1 3
8 4
6 1
7 2
1 1
5
1 8 4
2 6 2
7 8 2
1 5 3
1 8 5

Sample Output 1

5
2
9
3
-1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資。 0
2 1~11 所有石頭的顏色皆相異。 40
3 0~43 無特別限制。 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 262144 65536 1 3
1 4000 262144 65536 2 3
2 4000 262144 65536 2 3
3 4000 262144 65536 2 3
4 4000 262144 65536 2 3
5 4000 262144 65536 2 3
6 4000 262144 65536 2 3
7 4000 262144 65536 2 3
8 4000 262144 65536 2 3
9 4000 262144 65536 2 3
10 4000 262144 65536 2 3
11 4000 262144 65536 2 3
12 4000 262144 65536 3
13 4000 262144 65536 3
14 4000 262144 65536 3
15 4000 262144 65536 3
16 4000 262144 65536 3
17 4000 262144 65536 3
18 4000 262144 65536 3
19 4000 262144 65536 3
20 4000 262144 65536 3
21 4000 262144 65536 3
22 4000 262144 65536 3
23 4000 262144 65536 3
24 4000 262144 65536 3
25 4000 262144 65536 3
26 4000 262144 65536 3
27 4000 262144 65536 3
28 4000 262144 65536 3
29 4000 262144 65536 3
30 4000 262144 65536 3
31 4000 262144 65536 3
32 4000 262144 65536 3
33 4000 262144 65536 3
34 4000 262144 65536 3
35 4000 262144 65536 3
36 4000 262144 65536 3
37 4000 262144 65536 3
38 4000 262144 65536 3
39 4000 262144 65536 3
40 4000 262144 65536 3
41 4000 262144 65536 3
42 4000 262144 65536 3
43 4000 262144 65536 3
Submit
Back to Top