C - 花壇の水やり 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、庭にある花壇の管理を任されました。

花壇には N 個の区画が一列に並んでおり、左から順に区画 1 、区画 2 、…、区画 N と番号が付けられています。最初、区画 i の土には A_i リットルの水分が含まれています。

高橋君はこれから M 回の作業を順番に行います。 j 回目（ 1 \leq j \leq M ）の作業では、区画 L_j から区画 R_j までの連続する範囲に含まれるすべての区画に対して、それぞれの水分量を D_j リットルだけ変化させます。すなわち、各区画の水分量に D_j を加えます（ D_j が正のときは水やり、負のときは排水を意味します）。

ただし、どの時点においても、各区画の水分量は 0 以上 10^{18} 以下であることが保証されています。

すべての作業が終了した後の、各区画の水分量をそれぞれ求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9 （ 1 \leq i \leq N ）
  • 1 \leq L_j \leq R_j \leq N （ 1 \leq j \leq M ）
  • -10^9 \leq D_j \leq 10^9 （ 1 \leq j \leq M ）
  • どの時点においても、各区画の水分量は 0 以上 10^{18} 以下である
  • 入力はすべて整数である

入力

N M
A_1 A_2 \ldots A_N
L_1 R_1 D_1
L_2 R_2 D_2
\vdots
L_M R_M D_M
  • 1 行目には、区画の個数を表す整数 N と、作業の回数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各区画の初期水分量を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 続く M 行で、各作業の内容が与えられる。
  • そのうち j 行目（入力全体では 2 + j 行目）には、 j 回目の作業の対象範囲の左端 L_j 、右端 R_j 、水分の増減量 D_j が、スペース区切りで与えられる。

出力

すべての作業が終了した後の、区画 1 から区画 N までの水分量を整数としてスペース区切りで 1 行に出力してください。

入力例 1

5 3
10 5 8 3 6
1 3 2
2 5 -1
4 4 5

出力例 1

12 6 9 7 5

入力例 2

8 5
100 200 300 400 500 600 700 800
1 8 -50
3 6 100
1 4 -30
5 8 200
2 7 10

出力例 2

20 130 330 430 760 860 860 950

入力例 3

10 8
1000000000 500000000 0 300000000 700000000 100000000 999999999 250000000 800000000 450000000
1 10 1000000000
3 7 -500000000
1 5 200000000
6 10 300000000
2 4 -100000000
8 10 -200000000
1 1 500000000
5 9 100000000

出力例 3

2700000000 1600000000 600000000 900000000 1500000000 1000000000 1899999999 1450000000 2000000000 1550000000

Score : 366 pts

Problem Statement

Takahashi has been put in charge of managing a flower bed in the garden.

The flower bed consists of N sections arranged in a row, numbered section 1, section 2, …, section N from left to right. Initially, the soil in section i contains A_i liters of moisture.

Takahashi will perform M operations in order. In the j-th operation (1 \leq j \leq M), for every section in the contiguous range from section L_j to section R_j, he changes the moisture level by D_j liters. That is, he adds D_j to the moisture level of each such section (a positive D_j means watering, and a negative D_j means draining).

It is guaranteed that at any point in time, the moisture level of each section is between 0 and 10^{18}, inclusive.

After all operations are completed, determine the moisture level of each section.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • -10^9 \leq D_j \leq 10^9 (1 \leq j \leq M)
  • At any point in time, the moisture level of each section is between 0 and 10^{18}, inclusive
  • All input values are integers

Input

N M
A_1 A_2 \ldots A_N
L_1 R_1 D_1
L_2 R_2 D_2
\vdots
L_M R_M D_M
  • The first line contains an integer N representing the number of sections and an integer M representing the number of operations, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the initial moisture levels of each section, separated by spaces.
  • The following M lines describe each operation.
  • The j-th of these lines (the (2 + j)-th line of the entire input) contains the left endpoint L_j, the right endpoint R_j, and the moisture change amount D_j for the j-th operation, separated by spaces.

Output

Print the moisture levels of sections 1 through N after all operations are completed, as integers separated by spaces, on a single line.

Sample Input 1

5 3
10 5 8 3 6
1 3 2
2 5 -1
4 4 5

Sample Output 1

12 6 9 7 5

Sample Input 2

8 5
100 200 300 400 500 600 700 800
1 8 -50
3 6 100
1 4 -30
5 8 200
2 7 10

Sample Output 2

20 130 330 430 760 860 860 950

Sample Input 3

10 8
1000000000 500000000 0 300000000 700000000 100000000 999999999 250000000 800000000 450000000
1 10 1000000000
3 7 -500000000
1 5 200000000
6 10 300000000
2 4 -100000000
8 10 -200000000
1 1 500000000
5 9 100000000

Sample Output 3

2700000000 1600000000 600000000 900000000 1500000000 1000000000 1899999999 1450000000 2000000000 1550000000