問題一覧 > 通常問題

No.2662 Installing Cell Towers

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

問題文

長さがNNの数列A=(a1,a2,,aN)A=(a_1,a_2,\dots,a_N)があります.はじめ,この数列の要素はすべて00です.
また,長さがMMの数列が2つ,P=(p1,p2,,pM),Q=(q1,q2,,qM)P=(p_1,p_2,\dots,p_M),Q=(q_1,q_2,\dots,q_M)として与えられます.

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

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

入力

N MN\ M
p1 q1p_1\ q_1
p2 q2p_2\ q_2
\vdots
pM qMp_M\ q_M

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

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

出力

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

サンプル

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

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

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。