結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 14:24:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,225 ms / 2,500 ms |
コード長 | 2,817 bytes |
コンパイル時間 | 1,099 ms |
コンパイル使用メモリ | 84,628 KB |
実行使用メモリ | 29,012 KB |
最終ジャッジ日時 | 2025-09-06 14:25:07 |
合計ジャッジ時間 | 49,821 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; using ll = long long; struct lazytree{ int N, iden, lazyiden; vector<ll> tree, lazy; int pow2(int n){ int ans=1; while(ans<n) ans*=2; return ans; } void build(vector<ll>& a, int n){ N=pow2(n); iden=0, lazyiden=0; tree.resize(2*N, iden), lazy.resize(2*N, lazyiden); for(int i=0; i<n; i++) tree[N+i]=a[i]; for(int i=N-1; i>=1; i--) tree[i]=tree[2*i]+tree[2*i+1]; } void eval(int k, int l, int r){ if(lazy[k]!=lazyiden){ tree[k]+=lazy[k]*(r-l+1); //lazy[k]の値に強制的に切り替えられるのがquery if(l!=r){ lazy[2*k]+=lazy[k]; lazy[2*k+1]+=lazy[k]; } lazy[k]=lazyiden; } } void update(int s, int t, ll x, int k=1, int l=1, int r=-1){ //s, tは1-indexed! if(r<0) r=N; eval(k, l, r); if(t<l||r<s) return; if(s<=l&&r<=t){ lazy[k]+=x; eval(k, l, r); return; } else{ int mid=(l+r)/2; update(s, t, x, 2*k, l, mid); update(s, t, x, 2*k+1, mid+1, r); tree[k]=tree[2*k]+tree[2*k+1]; } return; } ll query(int s, int t, int k=1, int l=1, int r=-1){ //s, tは1-indexed! if(r<0) r=N; eval(k, l, r); if(t<l||r<s) return iden; if(s<=l&&r<=t) return tree[k]; int mid=(l+r)/2; ll A=query(s, t, 2*k, l, mid); ll B=query(s, t, 2*k+1, mid+1, r); return A+B; } }; int main(void){ int n, m; cin >> n >> m; vector<ll> a(n), l(n), r(n), b(m), po(m), house(n); for(int i=0; i<n; i++) cin >> a[i] >> l[i] >> r[i], house[i]=i+1, po[i]=a[i]; int q; cin >> q; lazytree seg, sum; seg.build(b, m); sum.build(po, m); for(int i=0; i<n; i++){ seg.update(l[i], r[i], 1); } ll ans=0; for(int i=0; i<n; i++){ ans+=a[i]*(r[i]-l[i]+1); ans-=a[i]*seg.query(house[i], house[i]); } //cout << ans << endl; while(q--){ int x, y, u, v; cin >> x >> y >> u >> v; x--; ans-=a[x]*(r[x]-l[x]+1); //cout << "A " << a[x]*(r[x]-l[x]+1) << endl; ans+=a[x]*seg.query(house[x], house[x]); //cout << "B " << a[x]*seg.query(house[x], house[x]) << endl; ans+=sum.query(l[x], r[x]); if(l[x]<=house[x]&&house[x]<=r[x]) ans-=a[x]; //cout << "C" << endl; sum.update(house[x], house[x], -a[x]); //cout << "D" << endl; seg.update(l[x], r[x], -1); l[x]=u, r[x]=v, house[x]=y; seg.update(l[x], r[x], 1); //cout << "E" << endl; sum.update(house[x], house[x], a[x]); ans-=sum.query(l[x], r[x]); if(l[x]<=house[x]&&house[x]<=r[x]) ans+=a[x]; ans+=a[x]*(r[x]-l[x]+1); //cout << "C " << a[x]*(r[x]-l[x]+1) << endl; ans-=a[x]*seg.query(house[x], house[x]); //cout << "D " << a[x]*seg.query(house[x], house[x]) << endl; cout << ans << '\n'; } return 0; }