Submit Info #15043

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

ケース詳細
Name Status Time Memory
example_00 AC 18 ms 28.66 MiB
max_random_00 AC 410 ms 29.61 MiB
max_random_01 AC 417 ms 29.55 MiB
max_random_02 AC 414 ms 29.66 MiB
medium_00 AC 20 ms 28.67 MiB
medium_01 AC 20 ms 28.75 MiB
medium_02 AC 19 ms 28.67 MiB
random_00 AC 304 ms 29.42 MiB
random_01 AC 302 ms 29.37 MiB
random_02 AC 208 ms 29.24 MiB
small_00 AC 20 ms 28.77 MiB
small_01 AC 21 ms 28.67 MiB
small_02 AC 20 ms 28.67 MiB
small_03 AC 20 ms 28.73 MiB
small_04 AC 19 ms 28.68 MiB
small_05 AC 19 ms 28.67 MiB
small_06 AC 20 ms 28.39 MiB
small_07 AC 19 ms 28.77 MiB
small_08 AC 18 ms 28.65 MiB
small_09 AC 19 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 chmx(ll m) { sum+=(m-mx)*mxc; mn=mn==mx ? m : mn; mn2=mn2==mx ? m : mn2; mx=m; } inline void chmn(ll m) { sum+=(m-mn)*mnc; mx=mx==mn ? m : mx; mx2=mx2==mn ? m : mx2; mn=m; } inline void down(const node& rhs, int d) { if(ll z=rhs.lz) sum+=z<<d, lz+=z, mx+=z, mx2+=z, mn+=z, mn2+=z; if(mx>rhs.mx) chmx(rhs.mx); if(mn<rhs.mn) chmn(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) { chmx(x); return true; } } else if(t==1) { if(x<=mn) return true; if(x<mn2) { chmn(x); return true; } } return false; } }; vector<node> A(1<<LG+1, {0, 0, -MX, -MX, MX, MX, 1, 1}); void build(int d=LG, int s=0, int i=1) { for(int i=0; i<N; i++) A[1<<LG|i].input(); for(int i=1<<LG; --i;) 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); cin>>N>>Q; build(); while(Q--) { cin>>t>>l>>r; x=0; if(t!=3) cin>>x; qry(); if(t==3) cout<<x<<'\n'; } }