C - Watering Duty Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は学校の園芸委員会に所属しています。校庭には東西方向に一直線に並んだ N 個のプランターがあり、西から順にプランター 1, プランター 2, \ldots, プランター N と番号が付けられています。水やりが始まる前の時点では、各プランターの水の量はすべて 0 リットルです。

今日から Q 日間、高橋君は水やり当番を担当することになりました。i 日目 (1 \leq i \leq Q) には、プランター L_i からプランター R_i まで（両端を含む）のそれぞれに C_i リットルずつの水を与えます。

Q 日間の水やりがすべて終わった後、プランター 1, プランター 2, \ldots, プランター N のそれぞれに与えられた水の合計量を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N
  • 1 \leq C_i \leq 10^4
  • 入力はすべて整数

入力

N Q
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_Q R_Q C_Q
  • 1 行目には、プランターの数 N と、水やりを行う日数 Q がスペース区切りで与えられる。
  • i + 1 行目 (1 \leq i \leq Q) には、i 日目に水を与えるプランターの番号の範囲の始点 L_i 、終点 R_i 、各プランターに与える水の量 C_i がスペース区切りで与えられる。

出力

N 個の整数をスペース区切りで 1 行に出力せよ。j 番目 (1 \leq j \leq N) の整数は、プランター j に与えられた水の合計量（リットル）を表す。すなわち、プランター 1 から順にプランター N までの合計量を出力せよ。

入力例 1

5 3
1 3 2
2 4 3
4 5 1

出力例 1

2 5 5 4 1

入力例 2

10 5
1 10 1
3 7 2
5 5 10
1 1 5
8 10 3

出力例 2

6 1 3 3 13 3 3 4 4 4

入力例 3

20 8
1 20 100
5 15 50
1 5 30
16 20 30
10 10 500
3 8 25
12 18 40
7 14 15

出力例 3

130 130 155 155 205 175 190 190 165 665 165 205 205 205 190 170 170 170 130 130

Score : 366 pts

Problem Statement

Takahashi is a member of the school gardening committee. In the schoolyard, there are N planters arranged in a straight line from east to west, numbered Planter 1, Planter 2, \ldots, Planter N from west to east. Before watering begins, the amount of water in each planter is 0 liters.

Starting today, Takahashi is assigned watering duty for Q days. On day i (1 \leq i \leq Q), he waters each planter from Planter L_i to Planter R_i (inclusive) with C_i liters of water.

After all Q days of watering are completed, find the total amount of water given to each of Planter 1, Planter 2, \ldots, Planter N.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N
  • 1 \leq C_i \leq 10^4
  • All input values are integers

Input

N Q
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_Q R_Q C_Q
  • The first line contains the number of planters N and the number of watering days Q, separated by a space.
  • The (i + 1)-th line (1 \leq i \leq Q) contains the starting planter number L_i, the ending planter number R_i, and the amount of water C_i given to each planter on day i, separated by spaces.

Output

Print N integers separated by spaces on a single line. The j-th integer (1 \leq j \leq N) represents the total amount of water (in liters) given to Planter j. That is, print the total amounts from Planter 1 through Planter N in order.

Sample Input 1

5 3
1 3 2
2 4 3
4 5 1

Sample Output 1

2 5 5 4 1

Sample Input 2

10 5
1 10 1
3 7 2
5 5 10
1 1 5
8 10 3

Sample Output 2

6 1 3 3 13 3 3 4 4 4

Sample Input 3

20 8
1 20 100
5 15 50
1 5 30
16 20 30
10 10 500
3 8 25
12 18 40
7 14 15

Sample Output 3

130 130 155 155 205 175 190 190 165 665 165 205 205 205 190 170 170 170 130 130