結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:11:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,653 ms / 2,500 ms |
コード長 | 2,127 bytes |
コンパイル時間 | 4,348 ms |
コンパイル使用メモリ | 257,892 KB |
実行使用メモリ | 23,540 KB |
最終ジャッジ日時 | 2025-09-06 14:12:08 |
合計ジャッジ時間 | 40,113 ms |
ジャッジサーバーID (参考情報) |
judge / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; #define int long long using S = long long; using F = long long; const S INF = 8e18; S op(S a, S b){ return std::max(a, b); } S e(){ return -INF; } S mapping(F f, S x){ return f+x; } F composition(F f, F g){ return f+g; } F id(){ return 0; } class SegTree{ public: int dat[800999],siz = 1; void init(int N){ siz = 1; while(siz < N) siz *= 2; for(int i = 1; i < siz*2; i++) dat[i] = 0; } void update(int pos, int x){ pos = pos + siz - 1; dat[pos] += x; while(pos >= 1){ pos /= 2; dat[pos] = dat[pos * 2] + dat[pos * 2 + 1]; } } int query(int l, int r, int a, int b, int u){ if(r <= a || b <= l) return 0; if(l <= a && b <= r) return dat[u]; int m = (a + b) / 2; int ansl = query(l,r,a,m,u*2); int ansr = query(l,r,m,b,u*2+1); return ansl + ansr; } }; signed main(){ int N,M; cin>>N>>M; vector<int> A(N+1); vector<pair<int,int>> B(N+1); vector<int> C(N+1); std::vector<S> v(M+10); atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v); SegTree Z; Z.init(M+10); int ans = 0; for(int i = 1; i <= N; i++){ cin>>A[i]>>B[i].first>>B[i].second; ans += A[i] * (B[i].second - B[i].first + 1); Z.update(i,A[i]); C[i] = i; seg.apply(B[i].first,B[i].second+1,1); } for(int i = 1; i <= N; i++) ans -= Z.query(B[i].first,B[i].second+1,1,Z.siz+1,1); int Q; cin>>Q; for(int i = 0; i < Q; i++){ int x,y,u,v; cin>>x>>y>>u>>v; //引っ越し前 seg.apply(B[x].first,B[x].second+1,-1); ans += Z.query(B[x].first,B[x].second+1,1,Z.siz+1,1); ans -= A[x] * (B[x].second - B[x].first + 1); ans += seg.get(C[x]) * A[x]; Z.update(C[x],-A[x]); //後 C[x] = y; B[x].first = u; B[x].second = v; Z.update(C[x],A[x]); ans -= seg.get(C[x]) * A[x]; ans += A[x] * (B[x].second - B[x].first + 1); ans -= Z.query(B[x].first,B[x].second+1,1,Z.siz+1,1); seg.apply(B[x].first,B[x].second+1,1); cout << ans << "\n"; } }