1919 . 王老先生

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

tmwilliamlin
我的中文很爛

User's AC Ratio

78.8% (52/66)

Submission's AC Ratio

26.0% (136/523)

Tags

CKsim 2016-CKsim-5th TOI 2015-TOI-2nd

Description

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

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

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

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

Input Format

第一行有三個正整數1≤n,m,Q≤105，分別代表王老先生僱用的人，有的農地數以及機器人拍照的次數。第二行有m個正整數1≤a1,a2,…,am≤n，代表農地的主人是誰。第三行有n個正整數1≤V1,V2,…,Vn≤109，代表n個人的目標。之後的Q行，每行有三個正整數1≤Lj≤Rj≤m,1≤Cj≤109，代表機器人拍了[Lj,Rj]這個區間，且這次被拍到的人會賺到Cj元。

子任務（測資） 額外限制 分數
1 (0~4) Lj=Rj 8
2 (5~9) m,Q≤104 13
3 (10~14) ai相異 37
4(0~19) 無 42

Output Format

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

Sample Input 1

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

Sample Output 1

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 (VSS, 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
Submit
Back to Top