結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 15:03:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 298 ms / 2,500 ms |
コード長 | 1,789 bytes |
コンパイル時間 | 3,435 ms |
コンパイル使用メモリ | 276,140 KB |
実行使用メモリ | 12,096 KB |
最終ジャッジ日時 | 2025-09-06 15:04:00 |
合計ジャッジ時間 | 14,213 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define ll long long const long long mod=998244353; const long long hmod=46216567629137; int N,M; ll bit1[200009],bit2[200009];//1がレート,2が人数 ll sum1(int i){ ll s=0; while(i>=1){ s+=bit1[i]; i-=i&-i; } return s; } void add1(int i,ll x){ while(i<=M){ bit1[i]+=x; i+=i&-i; } } ll sum2(int i){ ll s=0; while(i>=1){ s+=bit2[i]; i-=i&-i; } return s; } void add2(int i,ll x){ while(i<=M){ bit2[i]+=x; i+=i&-i; } } int main(){ cin.tie(0)->sync_with_stdio(0); cout.tie(0); cin>>N>>M; ll A[N+1],L[N+1],R[N+1]; for(int i=1;i<=N;i++) cin>>A[i]>>L[i]>>R[i]; int pos[N+1]; for(int i=1;i<=N;i++) pos[i]=i; for(int i=1;i<=M;i++){ bit1[i]=0; bit2[i]=0; } for(int i=1;i<=N;i++){ add1(i,A[i]); add2(L[i],1); add2(R[i]+1,-1); } ll ans=0; for(int i=1;i<=N;i++){ ans+=A[i]*(R[i]-L[i]+1); ans-=sum1(R[i])-sum1(L[i]-1); } int Q; cin>>Q; for(int z=1;z<=Q;z++){ ll X,Y,U,V; cin>>X>>Y>>U>>V; ans-=A[X]*(R[X]-L[X]+1); ans+=sum1(R[X])-sum1(L[X]-1); ans+=A[X]*(sum2(pos[X])); if(L[X]<=pos[X] && pos[X]<=R[X]) ans-=A[X]; //もと居たところの削除 add1(pos[X],-A[X]); add2(R[X]+1,1); add2(L[X],-1); L[X]=U; R[X]=V; pos[X]=Y; //追加 add1(Y,A[X]); add2(U,1); add2(V+1,-1); ans+=A[X]*(V-U+1); ans-=sum1(V)-sum1(U-1); ans-=sum2(Y)*A[X]; if(U<=Y && Y<=V) ans+=A[X]; cout<<ans<<"\n"; } }