C - Battery Remaining Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 台のスマートフォンを管理しています。スマートフォンには 1 から N までの番号が付けられており、スマートフォン i (1 \leq i \leq N) の初期バッテリー残量は S_i です。

これらのスマートフォンは、アプリの通知を受け取ることでバッテリーを消費します。ある日、Q 回の通知イベントが 1 番目から Q 番目まで順番に発生しました。j 番目 (1 \leq j \leq Q) の通知イベントでは、番号が L_j 以上 R_j 以下であるすべてのスマートフォンのバッテリー残量がそれぞれ 1 減少します。ただし、バッテリー残量が 0 のスマートフォンは 0 のまま変化しません。すなわち、通知イベントの対象となるスマートフォンのバッテリー残量を b とすると、b は \max(b - 1,\ 0) に変化します。

すべての通知イベントが終了した後の、各スマートフォンの最終的なバッテリー残量を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
  • 入力はすべて整数

入力

N Q
S_1 S_2 \ldots S_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 1 行目には、スマートフォンの台数を表す整数 N と、通知イベントの回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各スマートフォンの初期バッテリー残量を表す整数 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
  • 続く Q 行のうち j 行目 (1 \leq j \leq Q) には、j 番目の通知イベントの対象となるスマートフォンの番号の範囲を表す整数 L_j と R_j が、スペース区切りで与えられる。

出力

すべての通知イベント終了後の各スマートフォンのバッテリー残量を、スマートフォン 1 から N の順にスペース区切りで 1 行で出力せよ。末尾に改行を入れること。

入力例 1

5 3
10 5 3 8 2
1 3
2 4
3 5

出力例 1

9 3 0 6 1

入力例 2

4 5
3 1 4 2
1 2
1 2
2 3
3 4
1 4

出力例 2

0 0 1 0

入力例 3

10 8
100 0 5 20 3 15 8 0 12 7
1 5
3 7
2 6
5 10
1 10
6 8
4 4
1 3

出力例 3

97 0 0 15 0 10 4 0 10 5

Score : 366 pts

Problem Statement

Takahashi manages N smartphones. The smartphones are numbered from 1 to N, and the initial battery level of smartphone i (1 \leq i \leq N) is S_i.

These smartphones consume battery by receiving app notifications. One day, Q notification events occurred in order from the 1-st to the Q-th. In the j-th (1 \leq j \leq Q) notification event, the battery level of every smartphone whose number is between L_j and R_j inclusive decreases by 1. However, a smartphone whose battery level is 0 remains at 0. That is, if the battery level of a smartphone targeted by the notification event is b, then b changes to \max(b - 1,\ 0).

Find the final battery level of each smartphone after all notification events have finished.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
  • All inputs are integers

Input

N Q
S_1 S_2 \ldots S_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains an integer N representing the number of smartphones and an integer Q representing the number of notification events, separated by a space.
  • The second line contains integers S_1, S_2, \ldots, S_N representing the initial battery levels of each smartphone, separated by spaces.
  • In the following Q lines, the j-th line (1 \leq j \leq Q) contains integers L_j and R_j representing the range of smartphone numbers targeted by the j-th notification event, separated by a space.

Output

Print the battery levels of all smartphones after all notification events have finished, in order from smartphone 1 to N, separated by spaces, on a single line. Include a newline at the end.

Sample Input 1

5 3
10 5 3 8 2
1 3
2 4
3 5

Sample Output 1

9 3 0 6 1

Sample Input 2

4 5
3 1 4 2
1 2
1 2
2 3
3 4
1 4

Sample Output 2

0 0 1 0

Sample Input 3

10 8
100 0 5 20 3 15 8 0 12 7
1 5
3 7
2 6
5 10
1 10
6 8
4 4
1 3

Sample Output 3

97 0 0 15 0 10 4 0 10 5