119 . 品質監控

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

72.7% (8/11)

Tags

ioicamp ioicamp-2023

Description

本題的記憶體限制較小，請留意記憶體限制。

小 Y 擁有一塊土地，這塊土地由左至右被切割成了 $M$ 塊，並從 $1$ 編號至 $M$。為了確保土地品質的優良性，小 Y 決定設立 $N$ 個監視器，其中：

  • 第 $i$ 個監視器會監控編號在區間 $[x_i, y_i]$ 內的土地。
  • 當第 $i$ 個監視器發現自己監控的土地有任何一塊的污染值大於等於 $k_i$ 時，則他會產生警報。

其中，一塊土地的污染值是一個數值，並會隨著事件的發生增加。一開始，土地的污染值都是 $0$，而你預測到未來會經過 $Q$ 個時間點，第 $i$ 個時間點會有一陣污染潮將編號在區間 $[l_i, r_i]$ 內的土地污染值都增加 $v_i$。

對於每個監視器，你能告訴小 Y 他第一次發出警報的時間點是什麼時候嗎？或是告訴小 Y 這個監視器永遠都不會發出警報。

Input Format

輸入第一行有三個正整數 $M, N, Q$，依序代表小 Y 的土地長度、小 Y 設立的監視器數量以及時間點數量。

接著 $N$ 行，第 $i$ 行三個正整數 $x_i, y_i, k_i$，代表第 $i$ 個監視器的資料。

接著 $Q$ 行，第 $i$ 行三個正整數 $l_i, r_i, v_i$，代表第 $i$ 個事件的數據。

  • $1 \leq N, M, Q \leq 10^ 5$
  • $1 \leq x_i \leq y_i \leq M$
  • $1 \leq l_i \leq r_i \leq M$
  • $1\leq v_i \leq 10^ 4$
  • $1\leq k_i \leq 10^ 9$

Output Format

輸出一行以單一空格隔開的 $N$ 個數字，第 $i$ 個數字代表第 $i$ 個監視器發出警報的時間點，若第 $i$ 個監視器總是不會發出警報，請在第 $i$ 個數字輸出 $-1$。

Sample Input 1

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

Sample Output 1

1 -1 4 3

Hints

Problem Source

IOICamp 2023 Day4 pB

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資。 0
2 0~11 $N\leq 10$。 30
3 0, 12~24 $N, Q\leq 10^ 4$。 50
4 0~47 無特別限制。 20

Testdata and Limits

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