Submit Info #19020

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

ケース詳細
Name Status Time Memory
example_00 AC 10 ms 16.70 MiB
max_random_00 AC 215 ms 17.55 MiB
max_random_01 AC 216 ms 17.55 MiB
max_random_02 AC 215 ms 17.55 MiB
medium_00 AC 11 ms 16.67 MiB
medium_01 AC 13 ms 16.67 MiB
medium_02 AC 14 ms 16.73 MiB
random_00 AC 157 ms 17.36 MiB
random_01 AC 155 ms 17.30 MiB
random_02 AC 112 ms 17.17 MiB
small_00 AC 11 ms 16.64 MiB
small_01 AC 10 ms 16.67 MiB
small_02 AC 11 ms 16.67 MiB
small_03 AC 9 ms 16.67 MiB
small_04 AC 11 ms 16.66 MiB
small_05 AC 10 ms 16.68 MiB
small_06 AC 12 ms 16.67 MiB
small_07 AC 9 ms 16.61 MiB
small_08 AC 11 ms 16.67 MiB
small_09 AC 5 ms 16.61 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, mn; inline void input() { cin>>sum; mx=mn=sum; } inline node operator+(const node& rhs) const { return { sum+rhs.sum, 0, max(mx, rhs.mx), min(mn, rhs.mn) }; } inline void down(const node& rhs, int d) { if(rhs.mx==rhs.mn) sum=(mx=mn=rhs.mx)<<d, lz=0; else if(ll z=rhs.lz) sum+=z<<d, lz+=z, mx+=z, mn+=z; } inline bool apply(int d) { if(t==3) { x+=sum; return true; } if(t==2) { sum+=x<<d, lz+=x, mx+=x, mn+=x; return true; } if(t==0) { if(x>=mx) return true; if(x<=mn) { sum=x<<d, lz=0, mx=mn=x; return true; } } else if(t==1) { if(x<=mn) return true; if(x>=mx) { sum=x<<d, lz=0, mx=mn=x; return true; } } return false; } }; vector<node> A(1<<LG+1, {0, 0, -MX, MX}); void build() { 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'; } }