TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

82.1% (23/28)

Submission's AC Ratio

36.0% (82/228)

Description

俗話說的好:「王老先生有塊地 yee呀yee呀喲」

雖然說王老先生有塊地,但他並不想種田,所以他僱用了$n$個人管理他的$m$塊農地(排成一列),編號1到$m$。雖然一個農地一定恰為一個人管理,但一個人可以管理很多農地,所以這些人也僱用了一些手下在他所管理的農地工作。

王老先生是個非常在乎工作效率的人,所以他給了$n$個人定了目標$V_1, V_2, \dots, V_n$,代表第$i$個人需要賺到$V_i$元。
王老先生也非常在乎他所僱用的人是否有在認真工作,所以他買了一台機器人,用來追蹤$n$個人的手下工作的情況。這台機器人每次會用照相機拍下某個區間$[L_j, R_j]$的情況以確保大家有在認真工作。對於第$i$個人,如果他有某個手下在區間$[L_j, R_j]$認真工作(也就是說他有一塊在區間$[L_j, R_j]$的農地),那麼他會賺到$C_j$元。然而,如果某個人有兩個以上的手下在區間內,那麼他還是只會賺到$C_j$元。

假設所有人都認真工作,那麼第$i$個人在第幾張照片後就達成目標(或無法達成目標)呢?

Input Format

第一行有三個正整數$1\leq n,m,Q\leq 10^ 5$,分別代表王老先生僱用的人,有的農地數以及機器人拍照的次數。第二行有$m$個正整數$1\leq a_1, a_2, \dots, a_m\leq n$,代表農地的主人是誰。第三行有$n$個正整數$1\leq V_1, V_2, \dots, V_n\leq 10^ 9$,代表$n$個人的目標。之後的$Q$行,每行有三個正整數$1\leq L_j\leq R_j\leq m ,1\leq C_j\leq 10^ 9$,代表機器人拍了$[L_j, R_j]$這個區間,且這次被拍到的人會賺到$C_j$元。

子任務(測資) 額外限制 分數
1 (0~4) $L_j = R_j$ 8
2 (5~9) $m, Q\leq 10^ 4$ 13
3 (10~14) $a_i$相異 37
4(0~19) 42

Output Format

請輸出$n$行。第$i$行輸出一個正整數$t$,代表第$i$個人在恰在拍第$t$次照後達到目標。若$Q$次以後還是無法達成目標,請輸出-1。

Sample Input

4 5 3
1 2 3 2 1
5 10 15 20
1 5 3
1 4 3
2 4 9

Sample Output

2
3
3
-1

Hints

第一次照相後所有人賺到的錢:
3, 3, 3, 0
第二次照相後所有人賺到的錢:
6, 6, 6, 0
第三次照相後所有人賺到的錢:
6, 15, 15, 0

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第五次模擬賽pE
題目取自2015 TOI第一階段選訓第二次模擬考pB

Subtasks

No. Testdata Range Score
1 0~4 8
2 5~9 13
3 10~14 37
4 0~19 42

Testdata and Limits

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