問題一覧 > 通常問題

No.2662 Installing Cell Towers

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : ymmtr(せるたわーしーぷ!)ymmtr(せるたわーしーぷ!) / テスター : 2bit2bit aplysiaistpaplysiaistp
0 ProblemId : 9294 / 自分の提出
問題文最終更新日: 2024-03-06 15:06:52

問題文

長さが$N$の数列$A=(a_1,a_2,\dots,a_N)$があります.はじめ,この数列の要素はすべて$0$です.
また,長さが$M$の数列が2つ,$P=(p_1,p_2,\dots,p_M),Q=(q_1,q_2,\dots,q_M)$として与えられます.

いまから,整数$i=1,2,\dots,M$のそれぞれについて次の操作を行います;

  • 整数$j=1,2,\dots,N$のそれぞれについて,$d=|p_i-j|$とおき,$a_j$に$max(0,q_i-d)$を加算する.
ここで,実数$s,t$に対し,$max(s,t)$を$s$と$t$のうち小さくないほうの値と定義します.
さて,これらの操作をすべて終えたときの数列$A$の各要素の値を答えてください.

入力

$N\ M$
$p_1\ q_1$
$p_2\ q_2$
$\vdots$
$p_M\ q_M$

入力は次の制約をすべて満たします.

  • $1\le N \le 10^5$
  • $1\le M \le 10^5$
  • $1\le p_i \le N$
  • $1\le q_i \le 10^9$
  • 入力はすべて整数である.

出力

左から順に$a_1,a_2,\dots,a_N$を空白区切りで出力してください。
最後に改行してください。

サンプル

サンプル1
入力
8 1
4 2
出力
0 0 1 2 1 0 0 0

この場合,$i=1$のときの操作だけが行われます.このとき,$q_i=q_1=2$です。
$j=1,2,6,7,8$のとき,いずれも$d=|p_i-j|=|4-j|\ge 2$となるので,$a_j$には$max(0,q_i-d)=max(0,2-d)=0$が加算されます.
$j=3,5$のとき,いずれも$d=1$となるので,$a_j$には$max(0,q_i-d)=max(0,2-1)=1$が加算されます.
$j=4$のとき,$d=0$となるので,$a_j$には$max(0,q_i-d)=max(0,2-0)=2$が加算されます.
以上より,最終的な数列$A$は上のようになります.

サンプル2
入力
8 1
2 3
出力
2 3 2 1 0 0 0 0

サンプル1と同様に操作します。

サンプル3
入力
9 2
1 100
9 100
出力
192 192 192 192 192 192 192 192 192

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。