結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | mugen_1337 |
提出日時 | 2021-03-30 14:02:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 224 ms / 3,000 ms |
コード長 | 5,512 bytes |
コンパイル時間 | 2,454 ms |
コンパイル使用メモリ | 210,188 KB |
実行使用メモリ | 11,496 KB |
最終ジャッジ日時 | 2024-05-07 17:21:38 |
合計ジャッジ時間 | 7,851 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 18 ms
5,376 KB |
testcase_03 | AC | 69 ms
11,392 KB |
testcase_04 | AC | 89 ms
5,376 KB |
testcase_05 | AC | 158 ms
11,392 KB |
testcase_06 | AC | 44 ms
7,400 KB |
testcase_07 | AC | 99 ms
11,392 KB |
testcase_08 | AC | 117 ms
7,424 KB |
testcase_09 | AC | 41 ms
11,392 KB |
testcase_10 | AC | 65 ms
7,296 KB |
testcase_11 | AC | 119 ms
11,264 KB |
testcase_12 | AC | 157 ms
11,392 KB |
testcase_13 | AC | 159 ms
11,392 KB |
testcase_14 | AC | 158 ms
11,392 KB |
testcase_15 | AC | 163 ms
11,392 KB |
testcase_16 | AC | 157 ms
11,392 KB |
testcase_17 | AC | 224 ms
11,264 KB |
testcase_18 | AC | 104 ms
11,392 KB |
testcase_19 | AC | 187 ms
11,392 KB |
testcase_20 | AC | 191 ms
11,376 KB |
testcase_21 | AC | 186 ms
11,392 KB |
testcase_22 | AC | 191 ms
11,392 KB |
testcase_23 | AC | 188 ms
11,392 KB |
testcase_24 | AC | 189 ms
11,392 KB |
testcase_25 | AC | 26 ms
5,376 KB |
testcase_26 | AC | 102 ms
11,496 KB |
testcase_27 | AC | 87 ms
11,392 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 998244353 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } template<typename Monoid> struct SegmentTree{ using F=function<Monoid(Monoid,Monoid)>; // private: int sz; vector<Monoid> seg; Monoid query(int a,int b,int k,int l,int r){ if(a<=l and r<=b) return seg[k]; if(b<=l or r<=a) return M0; Monoid L=query(a,b,2*k,l,(l+r)/2); Monoid R=query(a,b,2*k+1,(l+r)/2,r); return f(L,R); } template<typename C> int find_first(int a,const C &check,Monoid &acc,int k,int l,int r){ if(k>=sz){ acc=f(acc,seg[k]); if(check(acc)) return -1; else return k-sz; } int m=(l+r)/2; if(m<=a) return find_first(a,check,acc,2*k+1,m,r); if(a<=l and check(f(acc,seg[k]))){ acc=f(acc,seg[k]); return -1; } int x=find_first(a,check,acc,2*k+0,l,m); if(x>=0) return x; return find_first(a,check,acc,2*k+1,m,r); } template<typename C> int find_last(int b,const C &check,Monoid &acc,int k,int l,int r){ if(k>=sz){ acc=f(acc,seg[k]); if(check(acc)) return -1; else return k-sz+1;//ここはfalse, +1した位置はtrue } int m=(l+r)/2; if(b<=m) return find_last(b,check,acc,2*k,l,m); if(r<=b and check(f(acc,seg[k]))){ acc=f(acc,seg[k]); return -1; } int x=find_last(b,check,acc,2*k+1,m,r); if(x>=0) return x; return find_last(b,check,acc,2*k,l,m); } public: F f; Monoid M0;// モノイドの元 SegmentTree(int n,F f,Monoid M0):f(f),M0(M0){ sz=1; while(sz<n)sz<<=1; seg.assign(2*sz,M0); } void set(int k,Monoid x){ seg[k+sz]=x; } void build(){ for(int k=sz-1;k>0;k--) seg[k]=f(seg[2*k],seg[2*k+1]); } void update(int k,Monoid x){ k+=sz; seg[k]=x; k>>=1; for(;k;k>>=1) seg[k]=f(seg[2*k],seg[2*k+1]); } Monoid query(int a,int b){ return query(a,b,1,0,sz); } // http://codeforces.com/contest/914/submission/107505449 // max x, check(query(a, x)) = true template<typename C> int find_first(int a,const C &check){ Monoid val=M0; return find_first(a,check,val,1,0,sz); } // http://codeforces.com/contest/914/submission/107505582 // min x, check(query(x, b)) = true template<typename C> int find_last(int b,C &check){ Monoid val=M0; return find_last(b,check,val,1,0,sz); } }; template<typename T> struct sums{ T sum_all,sum_l,sum_r,sum_max; sums():sum_all(0),sum_l(0),sum_r(0),sum_max(0){} sums(T sum_all,T sum_l,T sum_r,T sum_max):sum_all(sum_all),sum_l(sum_l),sum_r(sum_r),sum_max(sum_max){} }; template<typename T> sums<T> f(sums<T> a,sums<T> b){ sums<T> c; c.sum_all=a.sum_all+b.sum_all; c.sum_l=max(a.sum_l,a.sum_all+b.sum_l); c.sum_r=max(b.sum_r,b.sum_all+a.sum_r); c.sum_max=max({a.sum_max,b.sum_max,a.sum_r+b.sum_l}); return c; } signed main(){ int n,q;cin>>n>>q; using S=sums<ll>; SegmentTree<S> seg(n,f<ll>,S(0,-LINF,-LINF,-LINF)); rep(i,n){ ll a;cin>>a; seg.set(i,sums(a,a,a,a)); } seg.build(); // rep(k,2*seg.sz) cout<<k<<" ! "<<seg.seg[k].sum_all<<" "<<seg.seg[k].sum_l<<" "<<seg.seg[k].sum_r<<" "<<seg.seg[k].sum_max<<endl; while(q--){ string t;cin>>t; if(t=="set"){ int idx;ll x;cin>>idx>>x;idx--; seg.update(idx,S(x,x,x,x)); }else{ int a,b,c,d;cin>>a>>b>>c>>d;a--,c--; if(c<=a) c=a; if(d<=b) b=d; if(b<c){ auto mid=seg.query(b,c); auto l=seg.query(a,b); auto r=seg.query(c,d); cout<<(l.sum_r+mid.sum_all+r.sum_l)<<"\n"; }else{ auto mid=seg.query(c,b); auto l=seg.query(a,c); auto r=seg.query(b,d); // cout<<mid.sum_all<<" ("<<mid.sum_l<<", "<<mid.sum_r<<" "<<mid.sum_max<<"\n"; // cout<<l.sum_all<<" ("<<l.sum_l<<", "<<l.sum_r<<" "<<l.sum_max<<"\n"; // cout<<r.sum_all<<" ("<<r.sum_l<<", "<<r.sum_r<<" "<<r.sum_max<<"\n"; ll res=-LINF; chmax(res,mid.sum_max); chmax(res,l.sum_r+mid.sum_l); chmax(res,mid.sum_r+r.sum_l); chmax(res,l.sum_r+mid.sum_all+r.sum_l); cout<<res<<"\n"; } } } return 0; }