結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 14:35:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,895 ms / 2,500 ms |
コード長 | 4,703 bytes |
コンパイル時間 | 3,956 ms |
コンパイル使用メモリ | 290,124 KB |
実行使用メモリ | 23,380 KB |
最終ジャッジ日時 | 2025-09-06 14:36:13 |
合計ジャッジ時間 | 46,187 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #include <atcoder/segtree> struct dcin{template<typename T>dcin&operator>>(T&x){return std::cin>>x,x--,*this;}}dcin; /* S mapping(F f,S x,int len) 長さlenの区間にfを作用させる F composition(F f,F g,int len) 下の遅延配列に更新する。 いまのところg、さらにfを作用させる。 */ template<typename S,auto op,auto e,typename F,auto mapping,auto composition,auto id> class lazy_segtree{ public: explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {} explicit lazy_segtree(const vector<S>& vec) : _n(vec.size()) { _size = 1; while(_size < _n)_size *= 2; dat.assign(2 * _size,e()); lz.assign(2 * _size,id()); for(int i = 0; i < _n;i++){ dat[_size + i] = vec[i]; } for(int i = _size - 1;i > 0;--i){ dat[i] = op(dat[2*i],dat[2*i + 1]); } } S product(int l,int r){ return product(l,r,1,0,_size); } void set(int p,S x){ update(p,p+1,id(),1,0,_size); int idx = p + _size; dat[idx] = x; while(1<idx){ int par = idx/2; dat[par] = op(dat[2*par],dat[2*par + 1]); } } S get(int p){ update(p,p+1,id(),1,0,_size); return dat[p + _size]; } //[l,r)に含まれるA[i]:=f(A[i]) void apply(int l,int r,F f){ assert(0 <= l && l <= r && r <= _n); if (l == r) return; update(l,r,f,1,0,_size); } int size(){ return _size; } private: S product(int l,int r,int idx,int segL,int segR){ if(r <= segL || segR <= l) return e();//[l,r)の外側。興味ない。 int seglen = segR - segL; if(l <= segL && segR <= r){ return dat[idx]; } push(idx,seglen); int mid = (segL + segR)/2; return op( product(l,r,2*idx,segL,mid) , product(l,r,2*idx + 1,mid,segR) ); } //[l,r)をちょうど覆うようなセグメントの遅延処理fを全部やる。 //ノードidxに注目する。そのノードは[segL,segR)。 void update(int l,int r,F f,int idx,int segL,int segR){ if(r <= segL || segR <= l) return;//[l,r)の外側。興味ない。 int seglen = segR - segL; if(l <= segL && segR <= r){//まるっと含まれる dat[idx] = mapping(f,dat[idx], seglen); lz[idx] = composition(f,lz[idx], seglen); //ここまで、ここからは遅延させておく。 return; } push(idx,seglen); int mid = (segL + segR)/2; update(l,r,f,2*idx,segL,mid); update(l,r,f,2*idx + 1,mid,segR); dat[idx] = op(dat[idx*2],dat[idx*2 + 1]); } //idxのdat,lzを下に伝える void push(int idx,int curlen){ if(lz[idx] == id())return; int mid = curlen/2; dat[2*idx] = mapping(lz[idx],dat[2*idx],curlen/2); lz[2*idx] = composition(lz[idx],lz[2*idx], curlen/2); dat[2*idx + 1] = mapping(lz[idx],dat[2*idx + 1],curlen/2); lz[2*idx + 1] = composition(lz[idx],lz[2*idx + 1], curlen/2); lz[idx] = id(); } int _n,_size; vector<S> dat; vector<F> lz; }; using S = ll; using F = ll; S op(S a,S b){ return a+b; } S e(){ return 0; } F mapping(F f,S x,int len){ return x + f*len; } F composition(F f,F g,int len){ return f+g; } F id(){ return 0; } int main(){ ll n,m,q; cin >> n >> m; vector<ll> rate(n),pos(n),l(n),r(n); lazy_segtree<S,op,e,F,mapping,composition,id> lst(m); iota(pos.begin(),pos.end(),0); for(ll i = 0;i<n;i++){ cin >> rate[i] >> l[i] >> r[i]; l[i]--; lst.apply(l[i],r[i],1); } atcoder::segtree<ll,[](ll a,ll b)-> ll {return a+b;},[]()-> ll {return 0;}> seg(m); for(ll i = 0;i<n;i++){ seg.set(i,rate[i]); } ll sum = 0; for(ll i = 0;i<n;i++){ sum += (r[i] - l[i])*rate[i] - seg.prod(l[i],r[i]); } cin >> q; while(q--){ ll x,y,u,v; dcin >> x >> y >> u; cin >> v; // ll sub = (r[x] - l[x])*rate[x] - seg.prod(l[x],r[x]); lst.apply(l[x],r[x],-1); ll add2 = lst.get(pos[x])*rate[x]; // seg.set(pos[x],0); pos[x] = y; seg.set(pos[x],rate[x]); tie(l[x],r[x]) = make_pair(u,v); // ll add = (r[x] - l[x])*rate[x] - seg.prod(l[x],r[x]); ll sub2 = lst.get(pos[x])*rate[x]; lst.apply(l[x],r[x],1); sum = sum - sub + add - sub2 + add2; // cout << sum << '\n'; } flush(cout); }