各地点 \(i\) の受信強度の合計 \(S_i\) を求めることができれば、それと \(T_i\) とを比較すればこの問題に正解できます。

各電波塔について、受信強度は地点 \(P_i\) が最大の \(B_i\) となり、全体で \(\dots,0,1,2,\dots,B_i-1,B_i,B_i-1,\dots,2,1,0,\dots\) という形になります。
この形の加算が高速に処理出来ればよいですが、愚直に処理しようとすると時間計算量が \(O(NM)\) となり間に合いません。どうすればよいでしょうか？

概略: \(1\) 次の項 \(d_{1,i}\) と定数項 \(d_{0,i}\) とを用意し、先ほどの一次式のような加算を定数個の点の更新に帰着させた後累積和を取ると全体で時間計算量 \(O(N+M)\) で処理できます。

先に、全ての加算が終わった後に以下のルールで求値することを決めておきます。

• 変数 \(c_1=0,c_0=0\) を用意する。
• \(i=1,2,\dots,N\) について以下を繰り返す。
  • \(c_0\) に \(d_{0,i}\) 加算する。
  • \(c_0\) に \(c_1\) 加算する。
  • \(c_1\) に \(d_{1,i}\) 加算する。
  • この時点での \(c_0\) が所望の \(S_i\) であるようにする。

\(d_{1,i}\) および \(c_1\) が \(1\) 次の項(傾き)を管理し、 \(d_{0,i}\) および \(c_0\) が定数項を管理するイメージです。

端点の処理を考えないでよい状況下では、 \(P_i,B_i\) の加算は以下のように処理できます。

• \(d_{1,P_i-B_i}\) に \(1\) 加算する。
• \(d_{1,B_i}\) から \(2\) 減算する。
• \(d_{1,P_i+B_i}\) に \(1\) 加算する。

こうすることで、求値ルールを適用した後に \(\dots,0,1,2,\dots,B_i-1,B_i,B_i-1,\dots,2,1,0,\dots\) の形の加算が実現できていることがわかります。

端点の処理は \(d_{0,i}\) を活用すると実現可能ですが、以降は読者への宿題とします(実装例に詳細が示してあります)。

時間計算量は \(O(N+M)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M;
  cin >> N >> M;
  vector<ll> T(N+2);
  for(ll i=1;i<=N;i++){
    cin >> T[i];
  }
  vector<ll> d1(N+2,0);
  vector<ll> d0(N+2,0);
  while(M--){
    ll P,B;
    cin >> P >> B;
    if(B>=P){
      d0[1]+=(B-P+1);
      d1[1]++;
    }
    else{
      d1[P-B]++;
    }
    d1[P]-=2;
    if(P+B<=N){
      d1[P+B]++;
    }
  }
  ll res=-8e18;
  ll c1=0,c0=0;
  for(ll i=1;i<=N;i++){
    c0+=d0[i];
    c0+=c1;
    c1+=d1[i];
    if(c0<=T[i]){
      res=max(res,c0);
    }
  }
  cout << res << "\n";
  return 0;
}