Submit Info #24027

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp Believe AC 916 ms 43.16 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_random_00 AC 903 ms 43.11 MiB
max_random_01 AC 908 ms 43.10 MiB
max_random_02 AC 916 ms 43.16 MiB
medium_00 AC 3 ms 0.84 MiB
medium_01 AC 3 ms 0.77 MiB
medium_02 AC 2 ms 0.65 MiB
random_00 AC 610 ms 22.34 MiB
random_01 AC 668 ms 42.55 MiB
random_02 AC 387 ms 11.67 MiB
small_00 AC 1 ms 0.65 MiB
small_01 AC 3 ms 0.66 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 1 ms 0.67 MiB
small_04 AC 1 ms 0.67 MiB
small_05 AC 2 ms 0.67 MiB
small_06 AC 1 ms 0.66 MiB
small_07 AC 1 ms 0.67 MiB
small_08 AC 1 ms 0.66 MiB
small_09 AC 1 ms 0.67 MiB

#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int,null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define ordered_set_pair tree<pair<int,int>,null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> #define ordered_set_mutiset tree<int,null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> typedef long long int ll; typedef long double ld; typedef unsigned long long int ull; typedef pair<int,int> pi; #define PI 3.1415926535897932384 #define FOR(i,vv,n) for(ll i=vv;i<n;i++) #define FORR(i,n,vv) for(ll i=n-1;i>=vv;i--) #define ve vector #define maxind(v) (max_element(v.begin(),v.end())-v.begin()) #define minind(v) (min_element(v.begin(),v.end())-v.begin()) #define maxe(v) *max_element(v.begin(),v.end()) #define mine(v) *min_element(v.begin(),v.end()) #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define eb emplace_back #define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define mp make_pair #define M 1000000007ll #define INF 1000000000000000000ll #define PRECISE cout.precision(18); #define BS(v,n) binary_search(v.begin(),v.end(),n) #define srt(v) sort(v.begin(),v.end()) #define rsrt(v) sort(v.begin(),v.end(),greater <ll>()) #define uni(v) v.resize(unique(v.begin(),v.end())-v.begin()) #define F first #define S second #define GET(i,p) get<p>(i) typedef pair<ll,ll> p2; typedef pair<p2,ll> p3; const ll maxn = (1<<18); ll upmi[2*maxn],upma[2*maxn],upadd[2*maxn]; p3 curma[2*maxn],curmi[2*maxn]; ll cursum[2*maxn]; void fun1(ll &x1,ll &x2,ll &x3){ if(x1==x2) x1=x3; } void fun2(ll & x1, ll x2){ if(x1>x2) x1=x2; } void fun3(ll & x1, ll x2){ if(x1<x2) x1=x2; } void fun4(ll &z, ll b){ if(z!=INF&&z!=-INF) z+=b; } void ini(ll st, ll sl, ll sr){ upmi[st]=INF;upma[st]=-INF; curma[st] = {{0,-INF},(sr-sl+1)}; curmi[st] = {{0,INF},sr-sl+1}; if(sl == sr){ return ; } ll mid = (sl+sr)/2; ini(2*st,sl,mid); ini(2*st+1,mid+1,sr); } void pushdown(ll st, ll sl, ll sr){ if(upmi[st]!=INF){ if(upmi[st]<curma[st].F.F){ cursum[st] += (-curma[st].F.F + upmi[st])*curma[st].S; fun1(curmi[st].F.F,curma[st].F.F,upmi[st]); fun1(curmi[st].F.S,curma[st].F.F,upmi[st]); curma[st].F.F = upmi[st]; if(sl!=sr){ FOR(j,0,2){ fun2(upmi[2*st+j],upmi[st]-upadd[2*st+j]); fun2(upma[2*st+j],upmi[2*st+j]); } } } upmi[st]=INF; } if(upma[st]!=-INF){ if(upma[st]>curmi[st].F.F){ cursum[st] += (-curmi[st].F.F + upma[st])*curmi[st].S; fun1(curma[st].F.F,curmi[st].F.F,upma[st]); fun1(curma[st].F.S,curmi[st].F.F,upma[st]); curmi[st].F.F = upma[st]; if(sl!=sr){ FOR(j,0,2){ fun3(upma[2*st+j],upma[st]-upadd[2*st+j]); fun3(upmi[2*st+j],upma[2*st+j]); } } } upma[st]=-INF; } if(upadd[st]!=0){ cursum[st]+= (sr-sl+1)*(upadd[st]); fun4(curmi[st].F.F,upadd[st]); fun4(curmi[st].F.S,upadd[st]); fun4(curma[st].F.F,upadd[st]); fun4(curma[st].F.S,upadd[st]); if(sl!=sr){ FOR(j,0,2){ upadd[2*st+j]+=upadd[st]; } } upadd[st]=0; } } ll query(ll st,ll sl, ll sr, ll l, ll r){ pushdown(st, sl, sr); if(sr<l||sl>r){ return 0; } if(sr==r && sl == l){ return cursum[st]; } ll mid=(sl+sr)/2; return query(2*st,sl,mid,l,min(mid,r)) + query(2*st+1,mid+1,sr,max(mid+1,l),r); } p3 combmax(p3 a, p3 b){ if(a>b) swap(a,b); if(a.F.F==b.F.F){ return {{a.F.F,max(a.F.S,b.F.S)},a.S+b.S}; } return {{b.F.F,max(a.F.F,b.F.S)},b.S}; } p3 combmin(p3 a,p3 b){ if(a<b) swap(a,b); if(a.F.F==b.F.F){ return {{a.F.F,min(a.F.S,b.F.S)},a.S+b.S}; } return {{b.F.F,min(a.F.F,b.F.S)},b.S}; } void pull(ll st){ cursum[st]=cursum[2*st]+cursum[2*st+1]; curma[st]=combmax(curma[2*st],curma[2*st+1]); curmi[st]=combmin(curmi[2*st],curmi[2*st+1]); } void update(ll st,ll sl, ll sr, ll t, ll l, ll r, ll b){ pushdown(st,sl,sr); if(sr<l||sl>r){ return; } if(sr<=r&&sl>=l){ if(t == 0){ if(curma[st].F.F <=b){return;} else if(curma[st].F.S<b){ upmi[st] = b; pushdown(st,sl,sr); return; } } if(t==1){ if(curmi[st].F.F >=b){return;} else if(curmi[st].F.S>b){ upma[st] = b; pushdown(st,sl,sr); return; } } if(t==2){ upadd[st] = b; pushdown(st,sl,sr); return; } } ll mid=(sl+sr)/2; update(2*st,sl,mid,t,l,min(r,mid),b); update(2*st+1,mid+1,sr,t,max(l,mid+1),r,b); pull(st); } int main(){ // #ifndef ONLINE_JUDGE // // for getting input from input.txt // freopen("input.txt", "r", stdin); // // for writing output to output.txt // freopen("output.txt", "w", stdout); // #endif FAST // PRECISE ll n,q; cin>>n>>q; ini(1,0,n-1); ve <ll> v(n); FOR(i,0,n){ cin>>v[i]; update(1,0,n-1,2,i,i,v[i]); } FOR(i1,0,q){ ll t; cin>>t; if(t==3){ ll l,r; cin>>l>>r; cout<<query(1,0,n-1,l,r-1)<<"\n"; } else{ ll l,r,b; cin>>l>>r>>b; r--; update(1,0,n-1,t,l,r,b); } } return 0; }