12 . 優惠券

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

95.3% (41/43)

Submission's AC Ratio

80.3% (53/66)

Tags

ioicamp ioicamp-2024

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

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 4~75 無其他限制 35

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1
1 3000 262144 65536 1
2 3000 262144 65536 1
3 3000 262144 65536 1
4 3000 262144 65536 2 6
5 3000 262144 65536 2 6
6 3000 262144 65536 2 6
7 3000 262144 65536 2 6
8 3000 262144 65536 2 6
9 3000 262144 65536 2 6
10 3000 262144 65536 2 6
11 3000 262144 65536 2 6
12 3000 262144 65536 2 6
13 3000 262144 65536 2 6
14 3000 262144 65536 2 6
15 3000 262144 65536 2 6
16 3000 262144 65536 2 6
17 3000 262144 65536 2 6
18 3000 262144 65536 3 4 6
19 3000 262144 65536 3 4 6
20 3000 262144 65536 3 4 6
21 3000 262144 65536 3 4 6
22 3000 262144 65536 3 4 6
23 3000 262144 65536 3 4 6
24 3000 262144 65536 3 4 6
25 3000 262144 65536 3 4 6
26 3000 262144 65536 3 4 6
27 3000 262144 65536 3 4 6
28 3000 262144 65536 3 4 6
29 3000 262144 65536 3 4 6
30 3000 262144 65536 3 4 6
31 3000 262144 65536 3 4 6
32 3000 262144 65536 3 4 6
33 3000 262144 65536 3 4 6
34 3000 262144 65536 4 6
35 3000 262144 65536 4 6
36 3000 262144 65536 4 6
37 3000 262144 65536 4 6
38 3000 262144 65536 4 6
39 3000 262144 65536 4 6
40 3000 262144 65536 4 6
41 3000 262144 65536 4 6
42 3000 262144 65536 4 6
43 3000 262144 65536 4 6
44 3000 262144 65536 4 6
45 3000 262144 65536 4 6
46 3000 262144 65536 4 6
47 3000 262144 65536 4 6
48 3000 262144 65536 5 6
49 3000 262144 65536 5 6
50 3000 262144 65536 5 6
51 3000 262144 65536 5 6
52 3000 262144 65536 5 6
53 3000 262144 65536 5 6
54 3000 262144 65536 5 6
55 3000 262144 65536 5 6
56 3000 262144 65536 5 6
57 3000 262144 65536 5 6
58 3000 262144 65536 5 6
59 3000 262144 65536 5 6
60 3000 262144 65536 5 6
61 3000 262144 65536 5 6
62 3000 262144 65536 6
63 3000 262144 65536 6
64 3000 262144 65536 6
65 3000 262144 65536 6
66 3000 262144 65536 6
67 3000 262144 65536 6
68 3000 262144 65536 6
69 3000 262144 65536 6
70 3000 262144 65536 6
71 3000 262144 65536 6
72 3000 262144 65536 6
73 3000 262144 65536 6
74 3000 262144 65536 6
75 3000 262144 65536 6
Submit
Back to Top