2150 . 塗鴉遊戲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

100.0% (9/9)

Submission's AC Ratio

19.3% (21/109)

Tags

CKcon 2020-CKcon 2020-CKcon-fin

Description

有 N 格一開始都是白色的格子，每個格子有一個穩定度 wi
另外有 M 個事件，每次事件有一個發生時刻 tj 還有一個影響範圍 [aj,bj] ，你會把所有穩定度介在 [aj,bj] 的格子塗成黑色
每單位時間，如果有 x 個格子是白色的就可以帶來金額 x 的收益
現在你有一些顏料，一單位的顏料可以在任何時候把任何一個格子塗白
定義 f(i) 是假如你使用至多 i 單位的顏料的話，在時間 [0,T] 內所帶來的最大收益
請輸出 (f(1)+f(2)+⋯+f(K))modD ，保證 D 是質數

Input Format

第一行有五個正整數 N,M,K,T,D
第二行有 N 個非負整數代表每個格子的穩定度 wi
接下來 M 行，每行有三個數字 tj,aj,bj 描述一個題敘中提到的的事件

N,M≤5×105;K≤1012;M≤T≤109;D≤109+9
∀1≤i≤N,0≤wi≤109
∀1≤j≤M,0≤tj<T,0≤aj≤bj≤109

Output Format

請輸出一個整數 X=(f(1)+f(2)+⋯+f(K))modD ，其中 AmodB 是 A 除以 B 所得到的餘數的意思，必須介在[0,D)之間。

Sample Input 1

3 3 1 7 65537
7 6 6
3 0 7
0 2 3
5 2 7

Sample Output 1

11

Sample Input 2

4 2 16 5 1000000007
953786207 77833809 557541985 371354477
4 210501738 902051751
1 97672504 271502190

Sample Output 2

319

Sample Input 3

7 9 79 78 3
54 90 95 66 49 75 60
60 28 68
71 30 80
33 40 89
36 22 27
51 67 80
30 28 99
53 75 82
48 25 39
13 15 99

Sample Output 3

1

Hints

注意 long long

範測第一筆中，三個格子都會在時刻 3 被塗成黑色，此時可以立刻使用一單位的顏料讓其中一個格子能繼續保持白色兩單位時間，也可以選擇在時刻 5 讓其中一個格子保持白色到時刻 7 ，總收益均為11。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2, 20, 22 N,M≤20;wi,aj,bj,tj,T,K≤500 6
2 3~5 N,M,K≤105;∀1≤j≤M,aj=bj;∀x≠y,wx≠wy 6
3 6~8, 20 N,M≤3000;K≤NM 10
4 9~11, 20~21 N,M,T≤20;K≤109 18
5 12~14, 20 N,M,T≤105;K=1 10
6 15~16, 20~22 N,M,K≤105 20
7 0~22 無其他限制 30

Testdata and Limits

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