2150 . 塗鴉遊戲
TopCoder
Description
有 $N$ 格一開始都是白色的格子，每個格子有一個穩定度 $w_i$
另外有 $M$ 個事件，每次事件有一個發生時刻 $t_j$ 還有一個影響範圍 $[a_j,b_j]$ ，你會把所有穩定度介在 $[a_j,b_j]$ 的格子塗成黑色
每單位時間，如果有 $x$ 個格子是白色的就可以帶來金額 $x$ 的收益
現在你有一些顏料，一單位的顏料可以在任何時候把任何一個格子塗白
定義 $f(i)$ 是假如你使用至多 $i$ 單位的顏料的話，在時間 $[0,T]$ 內所帶來的最大收益
請輸出 $(f(1)+f(2)+\dots+f(K)) \mod D$ ，保證 $D$ 是質數
Input Format
第一行有五個正整數 $N, M, K, T, D$
第二行有 $N$ 個非負整數代表每個格子的穩定度 $w_i$
接下來 $M$ 行，每行有三個數字 $t_j, a_j, b_j$ 描述一個題敘中提到的的事件
$N, M \leq 5 \times 10^ 5; K \leq 10^ {12}; M \leq T \leq 10^ 9; D \leq 10^ 9 + 9$
$\forall 1 \leq i \leq N, 0 \leq w_i \leq 10^ 9$
$\forall 1 \leq j \leq M, 0 \leq t_j < T, 0 \leq a_j \leq b_j \leq 10^ 9$
Output Format
請輸出一個整數 $X=(f(1)+f(2)+\dots+f(K)) \mod D$ ，其中 $A \mod B$ 是 $A$ 除以 $B$ 所得到的餘數的意思，必須介在$[0,D)$之間。
Sample Input 1
7 6 6
3 0 7
0 2 3
5 2 7
Sample Output 1
Sample Input 2
953786207 77833809 557541985 371354477
4 210501738 902051751
1 97672504 271502190
Sample Output 2
Sample Input 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
Hints
注意 long long
範測第一筆中，三個格子都會在時刻 3 被塗成黑色，此時可以立刻使用一單位的顏料讓其中一個格子能繼續保持白色兩單位時間，也可以選擇在時刻 5 讓其中一個格子保持白色到時刻 7 ，總收益均為11。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2, 20, 22 | $N,M \leq 20; w_i, a_j, b_j, t_j, T, K \leq 500$ | 6 |
| 2 | 3~5 | $N, M, K \leq 10^ 5; \forall 1 \leq j \leq M, a_j = b_j; \forall x \neq y, w_x \neq w_y$ | 6 |
| 3 | 6~8, 20 | $N, M \leq 3000; K \leq NM$ | 10 |
| 4 | 9~11, 20~21 | $N,M,T \leq 20; K \leq 10^ 9$ | 18 |
| 5 | 12~14, 20 | $N,M,T \leq 10^ 5; K= 1$ | 10 |
| 6 | 15~16, 20~22 | $N,M,K \leq 10^ 5$ | 20 |
| 7 | 0~22 | 無其他限制 | 30 |