Submit Info #42947

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

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 1053 ms 15.36 MiB
max_random_01 AC 1054 ms 15.30 MiB
max_random_02 AC 1054 ms 15.30 MiB
medium_00 AC 7 ms 0.73 MiB
medium_01 AC 4 ms 0.67 MiB
medium_02 AC 3 ms 0.70 MiB
random2_00 AC 1577 ms 3.20 MiB
random2_01 AC 1567 ms 3.17 MiB
random2_02 AC 1570 ms 3.23 MiB
random3_00 AC 1970 ms 2.27 MiB
random3_01 AC 2119 ms 2.28 MiB
random3_02 AC 1973 ms 2.30 MiB
random_00 AC 699 ms 10.17 MiB
random_01 AC 736 ms 11.68 MiB
random_02 AC 482 ms 4.91 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 1 ms 0.70 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 1 ms 0.64 MiB
small_04 AC 5 ms 0.67 MiB
small_05 AC 1 ms 0.68 MiB
small_06 AC 2 ms 0.71 MiB
small_07 AC 1 ms 0.67 MiB
small_08 AC 2 ms 0.67 MiB
small_09 AC 1 ms 0.67 MiB

#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC optimize "unroll-loops" //#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,avx2,fma,mmx,popcnt,tune=native" //#pragma GCC optimize "prefetch-loop-arrays" using namespace std; using namespace __gnu_pbds; #define foru(i,a,b) for(int i=(a);i<(b);i++) #define ford(i,a,b) for(int i=(a);i>=(b);i--) #define fori(a,b) foru(i,a,b) #define forj(a,b) foru(j,a,b) #define fork(a,b) foru(k,a,b) #define seto(x,i) memset(x,i,sizeof x) #define pf first #define ps second #define pb push_back #define eb emplace_back #define em emplace #define mp make_pair #define mt make_tuple #define popcount __builtin_popcount #define popcountll __builtin_popcountll #define clz __builtin_clz #define clzll __builtin_clzll #define ctz __builtin_ctz #define ctzll __builtin_ctzll #define P2(x) (1LL<<(x)) #define sz(x) (int)x.size() #define all(x) begin(x),end(x) #if __SIZEOF_INT128__ typedef __int128_t i128; typedef __uint128_t ui128; #else typedef int64_t i128; typedef uint64_t ui128; #endif typedef int64_t ll; typedef uint64_t ull; typedef int8_t byte; typedef long double lld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<lld,lld> pdd; template<class T1,class T2> using ordered_map=tree<T1,T2,less<T1>,rb_tree_tag,tree_order_statistics_node_update>; template<class T1> using ordered_set=ordered_map<T1,null_type>; template<class T> using minpq=std::priority_queue<T,vector<T>,greater<T>>; template<class T> using maxpq=std::priority_queue<T,vector<T>,less<T>>; template<class T> using minpairingheap=__gnu_pbds::priority_queue<T,greater<T>,pairing_heap_tag>; template<class T>using maxpairingheap=__gnu_pbds::priority_queue<T,less<T>,pairing_heap_tag>; const int inf=0x3f3f3f3f,MOD=1e9+7; const ll INF=0x3f3f3f3f3f3f3f3f; const lld PI=acos((lld)-1); const ll SEED=443214^chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(); mt19937 randgen(SEED); int randint(int a, int b){return uniform_int_distribution<int>(a,b)(randgen);} ll randll(ll a, ll b){return uniform_int_distribution<ll>(a,b)(randgen);} ll gcd(ll a, ll b){return b?gcd(b,a%b):a;} ll fpow(ll a,ll b,ll M=MOD){ll ret=1;for(;b;b>>=1){if(b&1) ret=ret*a%M;a=a*a%M;}return ret;} template<class T1,class T2>constexpr const auto _min(const T1&x,const T2&y){return x<y?x:y;} template<class T,class...Ts>constexpr auto _min(const T&x,const Ts&...xs){return _min(x,_min(xs...));} template<class T1,class T2>constexpr const auto _max(const T1&x,const T2&y){return x>y?x:y;} template<class T,class...Ts>constexpr auto _max(const T&x,const Ts&...xs){return _max(x,_max(xs...));} #define min(...) _min(__VA_ARGS__) #define max(...) _max(__VA_ARGS__) template<class T1,class T2>constexpr bool ckmin(T1&x,const T2&y){return x>y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmin(T&x,const Ts&...xs){return ckmin(x,min(xs...));} template<class T1,class T2>constexpr bool ckmax(T1&x,const T2&y){return x<y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmax(T&x,const Ts&...xs){return ckmax(x,max(xs...));} struct chash{ static ll splitmix64(ll x){x+=0x9e3779b97f4a7c15; x=(x^(x>>30))*0xbf58476d1ce4e5b9; x=(x^(x>>27))*0x94d049bb133111eb; return x^(x>>31);} template<class T> size_t operator()(const T &x) const{return splitmix64(hash<T>()(x)+SEED);} template<class T1,class T2> size_t operator()(const pair<T1,T2>&x)const{return 31*operator()(x.first)+operator()(x.second);}}; void fIn(string s){freopen(s.c_str(),"r",stdin);} void fOut(string s){freopen(s.c_str(),"w",stdout);} void fIO(string s){fIn(s+".in"); fOut(s+".out");} string to_string(char c){return string(1,c);} string to_string(char* s){return (string)s;} string to_string(string s){return s;} template<class T> string to_string(complex<T> c){stringstream ss; ss<<c; return ss.str();} template<class T1,class T2> string to_string(pair<T1,T2> p){return "("+to_string(p.pf)+","+to_string(p.ps)+")";} template<size_t SZ> string to_string(bitset<SZ> b){string ret=""; fori(0,SZ) ret+=char('0'+b[i]); return ret;} template<class T> string to_string(T v){string ret="{"; for(const auto& x:v) ret+=to_string(x)+","; return ret+"}";} void DBG(){cerr<<"]"<<endl;} template<class T,class... Ts> void DBG(T x,Ts... xs){cerr<<to_string(x); if(sizeof...(xs)) cerr<<", "; DBG(xs...);} #ifdef LOCAL #define dbg(...) cerr<<"Line("<< __LINE__<<") -> ["<<#__VA_ARGS__<<"]: [", DBG(__VA_ARGS__) #else #define dbg(...) 0 #endif #define nl "\n" const int N=200010,M=MOD,B=450,R=N/B+10; ll n,q,t,a,b,c,l,r,bl,br,v,s[R],mi[R],ma[R],sum[R],arr[N]; map<ll,int> bv[R]; void push(int x){ if(x<0) return; if(mi[x]==-INF&&ma[x]==INF&&s[x]==0) return; fori(x*B,min(n,x*B+B)) arr[i]=min(max(arr[i],mi[x]),ma[x])+s[x]; mi[x]=-INF; ma[x]=INF; s[x]=0; } void pull(int x){ if(x<0) return; sum[x]=0; bv[x].clear(); fori(x*B,min(n,x*B+B)) sum[x]+=arr[i],bv[x][arr[i]]++; mi[x]=-INF; ma[x]=INF; s[x]=0; } int main(){ cin.tie(0)->sync_with_stdio(0); cin>>n>>q; fori(0,n) cin>>arr[i]; fori(0,R) pull(i); fori(0,q){ cin>>t>>l>>r; r--; if(t<3) cin>>v; if(t==0){ bl=(l+B-1)/B; br=(r+1)/B; if(bl>=br){ push(l/B); if(l/B!=r/B) push(r/B); forj(l,r+1) ckmin(arr[j],v); pull(l/B); if(l/B!=r/B) pull(r/B); continue; } forj(bl,br){ v-=s[j]; ckmin(mi[j],v); ckmin(ma[j],v); for(a=0;sz(bv[j])&&bv[j].rbegin()->pf>ma[j];bv[j].erase(bv[j].rbegin()->pf)){ auto x=*bv[j].rbegin(); a+=x.ps; sum[j]-=x.pf*x.ps; } sum[j]+=a*ma[j]; bv[j][ma[j]]+=a; v+=s[j]; } push(bl-1); forj(l,bl*B) ckmin(arr[j],v); pull(bl-1); push(br); forj(br*B,r+1) ckmin(arr[j],v); pull(br); } if(t==1){ bl=(l+B-1)/B; br=(r+1)/B; if(bl>=br){ push(l/B); if(l/B!=r/B) push(r/B); forj(l,r+1) ckmax(arr[j],v); pull(l/B); if(l/B!=r/B) pull(r/B); continue; } forj(bl,br){ v-=s[j]; ckmax(mi[j],v); ckmax(ma[j],v); for(a=0;sz(bv[j])&&bv[j].begin()->pf<mi[j];bv[j].erase(bv[j].begin()->pf)){ auto x=*bv[j].begin(); a+=x.ps; sum[j]-=x.pf*x.ps; } v+=s[j]; sum[j]+=a*mi[j]; bv[j][mi[j]]+=a; } push(bl-1); forj(l,bl*B) ckmax(arr[j],v); pull(bl-1); push(br); forj(br*B,r+1) ckmax(arr[j],v); pull(br); } if(t==2){ bl=(l+B-1)/B; br=(r+1)/B; if(bl>=br){ push(l/B); if(l/B!=r/B) push(r/B); forj(l,r+1) arr[j]+=v; pull(l/B); if(l/B!=r/B) pull(r/B); continue; } forj(bl,br){ s[j]+=v; sum[j]+=v*B; } push(bl-1); forj(l,bl*B) arr[j]+=v; pull(bl-1); push(br); forj(br*B,r+1) arr[j]+=v; pull(br); } if(t==3){ a=0; bl=(l+B-1)/B; br=(r+1)/B; if(bl>=br){ push(l/B); if(l/B!=r/B) push(r/B); forj(l,r+1) a+=arr[j]; pull(l/B); if(l/B!=r/B) pull(r/B); cout<<a<<nl; continue; } forj(bl,br){ a+=sum[j]; } push(bl-1); forj(l,bl*B) a+=arr[j]; pull(bl-1); push(br); forj(br*B,r+1) a+=arr[j]; pull(br); cout<<a<<nl; } } return 0; } /** */