結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー DeltaStruct
提出日時 2025-08-18 08:17:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 670 ms / 2,500 ms
コード長 1,368 bytes
コンパイル時間 2,063 ms
コンパイル使用メモリ 198,868 KB
実行使用メモリ 13,540 KB
最終ジャッジ日時 2025-09-06 12:34:12
合計ジャッジ時間 20,278 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
  ios::sync_with_stdio(false),cin.tie(0);
  int n,m; cin >> n >> m; vector<long long> segtree0(2*m),segtree1(2*m),A(n); vector<int> L(n),R(n),C(n);
  long long res(0);
  for (int i(0);i < n;++i){
    cin >> A[i] >> L[i] >> R[i]; --L[i],segtree1[m+i] = A[i],res += (R[i]-L[i])*A[i],C[i] = i;
    for (int l(m+L[i]),r(m+R[i]);l < r;l>>=1,r>>=1){
      if (l&1) ++segtree0[l++];
      if (r&1) ++segtree0[--r];
    }
  }
  for (int i(m-1);i;--i) segtree1[i] = segtree1[i<<1]+segtree1[i<<1|1];
  for (int i(0);i < n;++i) for (int l(m+L[i]),r(m+R[i]);l < r;l>>=1,r>>=1){
    if (l&1) res -= segtree1[l++];
    if (r&1) res -= segtree1[--r];
  }
  int q; cin >> q;
  while(q--){
    int i; cin >> i; --i,res -= (R[i]-L[i])*A[i];
    for (int l(m+C[i]);l;l>>=1) res += segtree0[l]*A[i],segtree1[l] -= A[i];
    for (int l(m+L[i]),r(m+R[i]);l < r;l>>=1,r>>=1){
      if (l&1) --segtree0[l],res += segtree1[l],++l;
      if (r&1) --r,--segtree0[r],res += segtree1[r];
    }
    cin >> C[i] >> L[i] >> R[i]; --C[i],--L[i],res += (R[i]-L[i])*A[i];
    for (int l(m+C[i]);l;l>>=1) res -= segtree0[l]*A[i],segtree1[l] += A[i];
    for (int l(m+L[i]),r(m+R[i]);l < r;l>>=1,r>>=1){
      if (l&1) ++segtree0[l],res -= segtree1[l],++l;
      if (r&1) --r,++segtree0[r],res -= segtree1[r];
    }
    cout << res << endl;
  }
}
0