12 . 優惠券
TopCoder
Tags
Description
在多魔櫻商店街中有一間和風點心店，小櫻非常喜歡那裡的草莓大福，常常會去那裡購買。為了促進買氣，那間店發行了優惠券，每購買一個草莓大福就可以使用一張。而小櫻一共有 $N$ 種優惠券，其中第 $i$ 種有 $c_i$ 張，可以在第 $l_i$ 天到第 $r_i$ 天使用，且每一張都可以打 $w_i$ 塊的折扣。
小櫻已經決定好連續 $M$ 天都要去點心店，其中第 $i$ 天預計會購買 $b_i$ 個草莓大福。而她會用以下方式使用優惠券：
- 若目前可以使用的優惠券數量不到 $b_i$，她會全部使用。
- 否則她會使用 $w_i$ 最大的 $b_i$ 張優惠券，若有多個相同的 $w_i$ 則她會使用種類編號最小的一張。
注意一張優惠券只能使用一次。
小櫻想要先知道每天她可以節省多少錢，請幫她解決這個問題。
Input Format
輸入第一行有兩個正整數 $N, M$，代表優惠券的種類數以及小櫻要去點心店的天數。
接下來 $N$ 行，每行有四個正整數 $l_i, r_i, c_i, w_i$，代表第 $i$ 種優惠券的資訊，變數意義與題目敘述相同。
接下來一行有 $M$ 個正整數 $b_1, b_2, \ldots, b_M$，變數意義與題目敘述相同。
- $1 \leq N, M \leq 5 \times 10^ 5$
- $1 \leq l_i \leq r_i \leq M$
- $1 \leq c_i, w_i, b_i \leq 10^ 9$
Output Format
請輸出一行，該行有 $M$ 個數字，其中第 $i$ 個為第 $i$ 天小櫻可以節省多少錢。
Sample Input 1
5 6 4 5 10 3 1 2 1 5 2 4 2 16 1 4 9 4 4 5 10 8 3 6 5 5 3 6
Sample Output 1
13 48 12 40 24 0
Sample Input 2
10 5 5 5 48763 864197532 2 2 4 6 1 1 2 4 1 1 1 2 1 1 3 1 3 3 3 7 2 2 10 10 3 3 4 1 4 4 2 8 4 4 4 5 5 3 4 7 56562
Sample Output 2
12 30 22 36 42140864252916
Sample Input 3
6 4 2 3 1 7 3 3 1 3 1 2 1 7 1 3 1 10 2 3 1 5 1 4 1 1 1 1 1 1
Sample Output 3
10 7 5 1
Sample Input 4
8 5 2 5 10 2 2 5 3 4 1 5 6 3 2 5 2 5 3 5 1 8 3 5 2 4 5 5 1 10 5 5 6 3 2 5 8 6 10
Sample Output 4
6 22 30 12 34
Hints
在第一筆範例測資中：
- 在第 $1$ 天時，小櫻會使用 $1$ 張可以打折 $5$ 塊的優惠券以及 $2$ 張可以打折 $4$ 塊的優惠券，總折扣為 $13$。
- 在第 $2$ 天時，小櫻會使用 $2$ 張可以打折 $16$ 塊的優惠券以及 $4$ 張可以打折 $4$ 塊的優惠券，總折扣為 $48$。
- 在第 $3$ 天時，小櫻會使用 $3$ 張可以打折 $4$ 塊的優惠券，總折扣為 $12$。
- 在第 $4$ 天時，小櫻會使用 $5$ 張可以打折 $8$ 塊的優惠券，總折扣為 $40$。
- 在第 $5$ 天時，小櫻會使用 $3$ 張可以打折 $8$ 塊的優惠券，總折扣為 $24$。
- 在第 $6$ 天時，小櫻沒有任何優惠券可以使用，總折扣為 $0$。
另外，第二筆範例測資符合 subtask 2，第三筆範例測資符合 subtask 3，第四筆範例測資符合 subtask 5，需要的人可以參考 > <
Problem Source
IOICamp 2024 PreExam pB
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | 範例測資 | 0 |
| 2 | 4~17 | $l_i = r_i$ | 10 |
| 3 | 18~33 | $1 \leq N, M \leq 2000, b_i = c_i = 1$ | 15 |
| 4 | 18~47 | $1 \leq N, M \leq 2000$ | 16 |
| 5 | 48~61 | $r_i = M$ | 24 |
| 6 | 0~75 | 無額外限制 | 35 |