Submit Info #17077

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp phibrain AC 427 ms 58.17 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_random_00 AC 424 ms 58.07 MiB
max_random_01 AC 427 ms 58.17 MiB
max_random_02 AC 423 ms 58.16 MiB
medium_00 AC 4 ms 0.92 MiB
medium_01 AC 4 ms 0.68 MiB
medium_02 AC 0 ms 0.74 MiB
random_00 AC 287 ms 37.42 MiB
random_01 AC 307 ms 44.01 MiB
random_02 AC 199 ms 16.28 MiB
small_00 AC 2 ms 0.68 MiB
small_01 AC 1 ms 0.67 MiB
small_02 AC 2 ms 0.68 MiB
small_03 AC 4 ms 0.72 MiB
small_04 AC 0 ms 0.68 MiB
small_05 AC 2 ms 0.67 MiB
small_06 AC 1 ms 0.68 MiB
small_07 AC 3 ms 0.67 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 1 ms 0.68 MiB

// I make this just for fun because i'm done // Aimi Haraguni >> Konomi Suzuki >> Yui >> Ikimono Gakari >> Garnidelia >> Kalafina >> Eir Aoi. .. dude? // problems that involves any kind of persistent data structures are the best of the best, are not them? // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define pb push_back #define ff first #define ss second #define tm1 first #define tm2 second.first #define tm3 second.second #define sz(x) ll(x.size()) #define all(v) (v).begin(), (v).end() // #define fill(x, v) memset(x, v, sizeof(x)) #define FER(i,a,b) for(ll i=ll(a); i < ll(b); ++i) #define IFR(i,a,b) for(ll i=ll(a); i>= ll(b); --i ) #define fastio ios_base::sync_with_stdio(0); cin.tie(0) #define N 210000 // #define M 19 // #define mod3 9 #define mod 998244353 #define mod1 1000000007 #define mod2 1000000009 #define bas 987625403 #define sqr(x) (x)*(x) #define INF 3000000000000000000 using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<ll, ll> ii; typedef pair<ll, ii > tri; typedef vector<ll> vi; typedef vector<vi> vv; typedef vector<ii> vii; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> S_t; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define trace(...) fff(#__VA_ARGS__, __VA_ARGS__) template<typename t> void fff(const char* x, t&& val1) { cout<<x<< " : "<<val1<<"\n";} template<typename t1, typename... t2> void fff(const char* x, t1&& val1, t2&&... val2){ const char* xd=strchr(x+1, ','); cout.write(x, xd-x)<<" : "<<val1<<" | "; fff(xd+1, val2...); } inline ll add(ll a, ll b) { return a+b < mod? a+b : a+b-mod;} inline ll rem(ll a, ll b) { return a >= b? a - b: a- b + mod;} inline ll mul(ll a, ll b) { return (long long) a*b%mod;} inline void Mul(ll &a, ll b) { a = (long long) a*b%mod;} inline ll bp(ll a, ll p){ ll ret; for(ret = 1; p; p>>=1, Mul(a, a)) (p & 1) && (Mul(ret, a), 1); return ret; } struct T{ ll fmx, fmn, smx, smn, cmx, cmn; ll sum, lval, add; T(){} T(ll fmx, ll fmn, ll smx, ll smn, ll cmx, ll cmn, ll sum): fmx(fmx), fmn(fmn), smx(smx), smn(smn), cmx(cmx), cmn(cmn), sum(sum){} inline void clear(){ lval=INF, add=0; } inline T Op(T a, T b){ if(a.fmx<b.fmx){ a.cmx=0; a.smx=a.fmx; a.fmx=b.fmx; } if(a.fmx==b.fmx){ a.cmx+=b.cmx; a.smx=max(a.smx, b.smx); } else a.smx=max(a.smx, b.fmx); if(a.fmn>b.fmn){ a.cmn=0; a.smn=a.fmn; a.fmn=b.fmn; } if(a.fmn==b.fmn){ a.cmn+=b.cmn; a.smn=min(a.smn, b.smn); } else a.smn=min(a.smn, b.fmn); a.sum+=b.sum; a.clear(); return a; } inline void UMax(ll x){ sum+=(x-fmn)*cmn; if(fmx==fmn) fmx=x; if(smx==fmn) smx=x; fmn=x; if(lval!=INF && lval<x) lval=x; } inline void Umin(ll x){ sum+=(x-fmx)*cmx; if(fmn==fmx) fmn=x; if(smn==fmx) smn=x; fmx=x; if(lval!=INF && lval>x) lval=x; } }; struct ST{ ll n; T lazy[4*N]; ll ar[N]; inline void updpro(T val , ll id, ll l, ll r){ if(val.fmx<lazy[id].fmx){ lazy[id].Umin(val.fmx); } if(val.fmn>lazy[id].fmn){ lazy[id].UMax(val.fmn); } } inline void updadd(ll val, ll id, ll l, ll r){ lazy[id].fmx+=val, lazy[id].fmn+=val; if(lazy[id].smx!=-INF) lazy[id].smx+=val; if(lazy[id].smn!=INF) lazy[id].smn+=val; lazy[id].sum+=val*(r-l); if(lazy[id].lval!=INF) lazy[id].lval+=val; else lazy[id].add+=val; } inline void updput(ll val ,ll id, ll l, ll r){ lazy[id].fmx=val, lazy[id].fmn=val; lazy[id].smx=-INF, lazy[id].smn=INF; lazy[id].cmx=r-l; lazy[id].cmn=r-l; lazy[id].sum=val*(r-l); lazy[id].lval=val; lazy[id].add=0; } inline void proh(ll id, ll l, ll r){ ll mid=(l+r)>>1; if(lazy[id].lval!=INF){ updput(lazy[id].lval, id<<1, l, mid); updput(lazy[id].lval, id<<1|1, mid, r); lazy[id].lval=INF; return; } if(lazy[id].add){ updadd(lazy[id].add, id<<1, l, mid); updadd(lazy[id].add, id<<1|1, mid, r); lazy[id].add=0; } updpro(lazy[id], id<<1, l, mid); updpro(lazy[id], id<<1|1, mid, r); } inline void UpdMin(ll x, ll y, ll val, ll id, ll l, ll r){ if(x>=r || y<=l || lazy[id].fmx<=val) return; if(x<=l && r<=y && lazy[id].smx<val && lazy[id].fmx > val){ lazy[id].Umin(val); return; } proh(id, l, r); ll mid=(l+r)>>1; UpdMin(x, y, val, id<<1, l, mid); UpdMin(x, y, val, id<<1|1, mid, r); lazy[id]=lazy[id].Op(lazy[id<<1], lazy[id<<1|1]); } inline void UpdMax(ll x, ll y, ll val, ll id, ll l, ll r){ if(x>=r || y<=l || lazy[id].fmn>=val) return; if(x<=l && r<=y && lazy[id].smn>val && lazy[id].fmn<val){ lazy[id].UMax(val); return; } proh(id, l, r); ll mid=(l+r)>>1; UpdMax(x, y, val, id<<1, l, mid); UpdMax(x, y, val, id<<1|1, mid, r); lazy[id]=lazy[id].Op(lazy[id<<1], lazy[id<<1|1]); } inline void UpdQue(ll x, ll y, ll val, ll id, ll l, ll r){ if(x>=r || y<=l) return; if(x<=l && r<=y){ updadd(val, id, l, r); return; } proh(id, l, r); ll mid=(l+r)>>1; UpdQue(x, y, val, id<<1, l, mid); UpdQue(x, y, val, id<<1|1, mid, r); lazy[id]=lazy[id].Op(lazy[id<<1], lazy[id<<1|1]); } inline void UpdPut(ll x, ll y, ll val, ll id, ll l, ll r){ if(x>=r || y<=l) return; if(x<=l && r<=y){ updput(val, id, l, r); return; } proh(id, l, r); ll mid=(l+r)>>1; UpdPut(x, y, val, id<<1, l, mid); UpdPut(x, y, val, id<<1|1, mid, r); lazy[id]=lazy[id].Op(lazy[id<<1], lazy[id<<1|1]); } inline ll getSum(ll x, ll y, ll id, ll l, ll r){ if(x>=r || y<=l) return 0; if(x<=l && r<=y) return lazy[id].sum; proh(id, l, r); ll mid=(l+r)>>1; ll left, right; left=getSum(x, y, id<<1, l , mid); right=getSum(x, y, id<<1|1, mid, r); return left + right; } inline void Build(ll id, ll l, ll r){ if(l>r) return; if(l+1==r){ lazy[id].sum=ar[l]; lazy[id].cmx=lazy[id].cmn=1; lazy[id].fmx=lazy[id].smx=-INF; lazy[id].fmn=lazy[id].smn=INF; lazy[id].fmx=lazy[id].fmn=ar[l]; lazy[id].clear(); return; } ll mid=(l+r)>>1; Build(id<<1, l, mid); Build(id<<1|1, mid, r); lazy[id]=lazy[id].Op(lazy[id<<1], lazy[id<<1|1]); } inline void updMax(ll x, ll y, ll val) { UpdMax(x, y, val, 1, 0, n);} inline void updMin(ll x, ll y, ll val) { UpdMin(x, y, val, 1, 0, n);} inline void updR(ll x, ll y, ll val) { UpdQue(x, y, val, 1, 0, n);} inline void updP(ll x, ll y, ll val) { UpdPut(x, y, val, 1, 0, n);} inline ll que(ll x, ll y) { return getSum(x, y, 1, 0, n);} inline void build() { FER(i, 0, n<<2) { lazy[i].clear(); } Build(1, 0, n); } }st; inline void read(ll &x) {cin>>x;} int main(){ fastio; ll n, q; read(n), read(q); st.n=n; FER(i,0,n) cin>>st.ar[i]; st.build(); ll l, r, x, t; FER(i,0,q){ cin>>t>>l>>r; if(t==0){ cin>>x; st.updMin(l, r, x); // FER(j,0,n) cout<<st.que(j, j+1)<<" "; cout<<endl; } else if(t==1){ cin>>x; st.updMax(l, r, x); // FER(j,0,n) cout<<st.que(j, j+1)<<" "; cout<<endl; } else if(t==2){ cin>>x; st.updR(l, r, x); } else{ x=st.que(l, r); cout<<x<<endl; } } return 0; }