Submit Info #14876

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp (anonymous) AC 434 ms 29.61 MiB

ケース詳細
Name Status Time Memory
example_00 AC 15 ms 28.67 MiB
max_random_00 AC 434 ms 29.61 MiB
max_random_01 AC 427 ms 29.58 MiB
max_random_02 AC 421 ms 29.55 MiB
medium_00 AC 17 ms 28.67 MiB
medium_01 AC 20 ms 28.67 MiB
medium_02 AC 18 ms 28.70 MiB
random_00 AC 309 ms 29.38 MiB
random_01 AC 319 ms 29.42 MiB
random_02 AC 213 ms 29.26 MiB
small_00 AC 16 ms 28.69 MiB
small_01 AC 16 ms 28.67 MiB
small_02 AC 16 ms 28.69 MiB
small_03 AC 15 ms 28.73 MiB
small_04 AC 17 ms 28.75 MiB
small_05 AC 17 ms 28.65 MiB
small_06 AC 16 ms 28.71 MiB
small_07 AC 17 ms 28.67 MiB
small_08 AC 19 ms 28.67 MiB
small_09 AC 16 ms 28.67 MiB

#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; using ll=long long; constexpr int LG=32-__builtin_clz(200000-1); constexpr ll MX=4e18; int N, M, Q, t, l, r; ll x; struct node { ll sum, lz, mx, mx2, mn, mn2; int mxc, mnc; inline void input() { cin>>sum; mx=mn=sum; } inline node operator+(const node& rhs) const { node n; n.sum=sum+rhs.sum; n.lz=0; n.mx2=max(mx2, rhs.mx2); if(mx<rhs.mx) { n.mx=rhs.mx, n.mxc=rhs.mxc; n.mx2=max(n.mx2, mx); } else { n.mx=mx, n.mxc=mxc; if(mx==rhs.mx) n.mxc+=rhs.mxc; else n.mx2=max(n.mx2, rhs.mx); } n.mn2=min(mn2, rhs.mn2); if(mn>rhs.mn) { n.mn=rhs.mn, n.mnc=rhs.mnc; n.mn2=min(n.mn2, mn); } else { n.mn=mn, n.mnc=mnc; if(mn==rhs.mn) n.mnc+=rhs.mnc; else n.mn2=min(n.mn2, rhs.mn); } return n; } inline void down(const node& rhs, int d) { ll z=rhs.lz; sum+=z<<d, lz+=z, mx+=z, mx2+=z, mn+=z, mn2+=z; if(mx>rhs.mx) { sum+=(rhs.mx-mx)*mxc; mn=mn==mx ? rhs.mx : mn; mn2=mn2==mx ? rhs.mx : mn2; mx=rhs.mx; } if(mn<rhs.mn) { sum+=(rhs.mn-mn)*mnc; mx=mx==mn ? rhs.mn : mx; mx2=mx2==mn ? rhs.mn : mx2; mn=rhs.mn; } } inline bool apply(int d) { if(t==3) { x+=sum; return true; } if(t==2) { sum+=x<<d, lz+=x, mx+=x, mx2+=x, mn+=x, mn2+=x; return true; } if(t==0) { if(x>=mx) return true; if(x>mx2) { sum+=(x-mx)*mxc; mn=mn==mx ? x : mn; mn2=mn2==mx ? x : mn2; mx=x; return true; } } else if(t==1) { if(x<=mn) return true; if(x<mn2) { sum+=(x-mn)*mnc; mx=mx==mn ? x : mx; mx2=mx2==mn ? x : mx2; mn=x; return true; } } return false; } }; vector<node> A; void build(int d=LG, int s=0, int i=1) { if(!d) return A[i].input(); int m=s|1<<--d; build(d, s, i*2); if(m<N) build(d, m, i*2+1); A[i]=A[i*2]+A[i*2+1]; } void qry(int d=LG, int s=0, int i=1) { if(l<=s && s+(1<<d)<=r && A[i].apply(d)) return; int m=s|1<<--d; A[i*2].down(A[i], d); A[i*2+1].down(A[i], d); if(l<m) qry(d, s, i*2); if(r>m) qry(d, m, i*2+1); A[i]=A[i*2]+A[i*2+1]; } int main() { ios::sync_with_stdio(0);cin.tie(0); A.resize(1<<LG+1, {0, 0, -MX, -MX, MX, MX, 1, 1}); cin>>N>>Q; build(); while(Q--) { cin>>t>>l>>r; x=0; if(t!=3) cin>>x; qry(); if(t==3) cout<<x<<'\n'; } }