Submission #537993

#TimeUsernameProblemLanguageResultExecution timeMemory
537993czhang2718Bitaro, who Leaps through Time (JOI19_timeleap)C++17
100 / 100
508 ms64508 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; struct P{ int l, r; ll k; inline P(){} inline P(int l, int r, ll k): l(l), r(r), k(k) {} inline friend P operator + (P a, P b){ if(a.k==-1 && b.k==-1){ if(max(a.l, b.l)<=min(a.r, b.r)) return P(max(a.l, b.l), min(a.r, b.r), -1); if(a.l>b.r) return P(a.l, b.r, a.l-b.r); if(a.r<b.l) return P(a.r, b.l, 0); } if(a.k==-1){ if(b.l>a.r) return P(a.r, b.r, b.k); if(b.l<a.l) return P(a.l, b.r, b.k+a.l-b.l); return b; } if(b.k==-1){ if(b.l>a.r) return P(a.l, b.l, a.k); if(b.r<a.r) return P(a.l, b.r, a.k+a.r-b.r); return a; } return P(a.l, b.r, a.k+b.k+max(0, a.r-b.l)); } }; const int N=300000; int n, q; struct segtree{ vector<P> seg; segtree(){ seg.resize(4*n); } void build(vector<P> &v, int x, int lx, int rx){ if(rx-lx==1){ seg[x]=v[lx]; return; } int m=(lx+rx)/2; build(v, 2*x+1, lx, m); build(v, 2*x+2, m, rx); seg[x]=seg[2*x+1]+seg[2*x+2]; // cout << "seg " << lx << " " << rx << " " << seg[x].l << " " << seg[x].r << " " << seg[x].k << "\n"; } void build(vector<P> v){ build(v, 0, 0, n-1); } void upd(int i, P p, int x, int lx, int rx){ if(rx-lx==1){ seg[x]=p; return; } int m=(lx+rx)/2; if(i<m) upd(i, p, 2*x+1, lx, m); else upd(i, p, 2*x+2, m, rx); seg[x]=seg[2*x+1]+seg[2*x+2]; } void upd(int i, P p){ upd(i, p, 0, 0, n-1); } P query(int l, int r, int x, int lx, int rx){ if(lx>=l && rx<=r) return seg[x]; if(lx>=r || rx<=l) return P(-1e9, 1e9, -1); int m=(lx+rx)/2; return query(l, r, 2*x+1, lx, m)+query(l, r, 2*x+2, m, rx); } P query(int l, int r){ return query(l, r, 0, 0, n-1); } }; int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> q; vector<P> path1, path2; segtree st1, st2; for(int i=0; i<n-1; i++){ int a, b; cin >> a >> b; path1.push_back(P(a-i, b-i-1, -1)); path2.push_back(P(a-(n-2-i), b-(n-2-i)-1, -1)); } if(n>1){ st1.build(path1); reverse(path2.begin(), path2.end()); st2.build(path2); } auto solve=[&](int a, int b, int c, int d, P p)->ll{ b-=a, d-=c; if(p.k==-1){ int x=b; x=max(x, p.l); x=min(x, p.r); return (ll)max(0, b-x)+max(0, x-d); } else return (ll)max(0, b-p.l)+p.k+max(0, p.r-d); }; while(q--){ int op; cin >> op; if(op==1){ int i, a, b; cin >> i >> a >> b; --i; st1.upd(i, P(a-i, b-i-1, -1)); st2.upd(n-2-i, P(a-(n-2-i), b-(n-2-i)-1, -1)); } else{ int a, b, c, d; cin >> a >> b >> c >> d; --a, --c; if(n==1){ cout << max(0, b-d) << "\n"; continue; } if(a==c) cout << max(0, b-d) << "\n"; if(a<c) cout << solve(a, b, c, d, st1.query(a, c)) << "\n"; if(a>c) cout << solve(n-1-a, b, n-1-c, d, st2.query(n-1-a, n-1-c)) << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...