Submit Info #14892

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

ケース詳細
Name Status Time Memory
example_00 AC 15 ms 28.67 MiB
max_random_00 AC 399 ms 29.62 MiB
max_random_01 AC 434 ms 29.59 MiB
max_random_02 AC 405 ms 29.56 MiB
medium_00 AC 17 ms 28.74 MiB
medium_01 AC 16 ms 28.67 MiB
medium_02 AC 16 ms 28.73 MiB
random_00 AC 283 ms 29.42 MiB
random_01 AC 316 ms 29.30 MiB
random_02 AC 196 ms 29.17 MiB
small_00 AC 16 ms 28.67 MiB
small_01 AC 17 ms 28.77 MiB
small_02 AC 16 ms 28.75 MiB
small_03 AC 18 ms 28.65 MiB
small_04 AC 20 ms 28.74 MiB
small_05 AC 14 ms 28.77 MiB
small_06 AC 15 ms 28.67 MiB
small_07 AC 18 ms 28.67 MiB
small_08 AC 15 ms 28.66 MiB
small_09 AC 16 ms 28.67 MiB

#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; using L=long long; constexpr L MX=4e18; int N, M, Q, t, l, r; L x; struct node { L sum, lz, mx, mx2, mn, mn2; int mxc, mnc; inline node operator+(const node& R) const { node n; n.sum=sum+R.sum; n.lz=0; n.mx2=max(mx2, R.mx2); if(mx==R.mx) n.mx=mx, n.mxc=mxc+R.mxc; else { n.mxc=mx<R.mx ? R.mxc : mxc; n.mx=mx<R.mx ? R.mx : mx; n.mx2=max(n.mx2, mx<R.mx ? mx : R.mx); } n.mn2=min(mn2, R.mn2); if(mn==R.mn) n.mn=mn, n.mnc=mnc+R.mnc; else { n.mnc=mn<R.mn ? mnc : R.mnc; n.mn=mn<R.mn ? mn : R.mn; n.mn2=min(n.mn2, mn<R.mn ? R.mn : mn); } return n; } inline void chmx(L m) { sum+=(m-mx)*mxc; mn=mn==mx ? m : mn; mn2=mn2==mx ? m : mn2; mx=m; } inline void chmn(L m) { sum+=(m-mn)*mnc; mx=mx==mn ? m : mx; mx2=mx2==mn ? m : mx2; mn=m; } inline void down(const node& R, int d) { if(L z=R.lz) sum+=z<<d, lz+=z, mx+=z, mx2+=z, mn+=z, mn2+=z; if(mx>R.mx) chmx(R.mx); if(mn<R.mn) chmn(R.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(x<=mn) return true; if(x<mn2) { chmn(x); return true; } } return false; } }; vector<node> A(1<<19, {0, 0, -MX, -MX, MX, MX, 1, 1}); void build(int d=18, int s=0, int i=1) { if(!d) { cin>>x; A[i].mx=A[i].mn=A[i].sum=x; return; } 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=18, 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'; } }