結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | hashiryo |
提出日時 | 2019-06-03 22:11:31 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 275 ms / 3,000 ms |
コード長 | 3,120 bytes |
コンパイル時間 | 1,914 ms |
コンパイル使用メモリ | 183,980 KB |
実行使用メモリ | 12,276 KB |
最終ジャッジ日時 | 2024-09-17 20:35:59 |
合計ジャッジ時間 | 8,167 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 25 ms
5,504 KB |
testcase_03 | AC | 93 ms
12,032 KB |
testcase_04 | AC | 108 ms
5,504 KB |
testcase_05 | AC | 186 ms
12,056 KB |
testcase_06 | AC | 56 ms
7,424 KB |
testcase_07 | AC | 122 ms
12,160 KB |
testcase_08 | AC | 141 ms
7,588 KB |
testcase_09 | AC | 60 ms
12,160 KB |
testcase_10 | AC | 83 ms
7,680 KB |
testcase_11 | AC | 152 ms
12,160 KB |
testcase_12 | AC | 196 ms
12,160 KB |
testcase_13 | AC | 198 ms
12,160 KB |
testcase_14 | AC | 197 ms
12,160 KB |
testcase_15 | AC | 195 ms
12,160 KB |
testcase_16 | AC | 194 ms
12,196 KB |
testcase_17 | AC | 275 ms
12,160 KB |
testcase_18 | AC | 142 ms
12,160 KB |
testcase_19 | AC | 230 ms
12,256 KB |
testcase_20 | AC | 230 ms
12,160 KB |
testcase_21 | AC | 234 ms
12,160 KB |
testcase_22 | AC | 232 ms
12,276 KB |
testcase_23 | AC | 231 ms
12,228 KB |
testcase_24 | AC | 228 ms
12,208 KB |
testcase_25 | AC | 52 ms
6,944 KB |
testcase_26 | AC | 141 ms
12,164 KB |
testcase_27 | AC | 121 ms
12,208 KB |
ソースコード
#include<bits/stdc++.h> #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef tuple<ll,ll> Pll; typedef vector<ll> vll; const ll INF = LLONG_MAX/10; const ll MOD = 1e9+7; template <typename T> struct SegmentTree{ using F = function<T(T,T)>; int n; F f; T ti; vector<T> dat; SegmentTree(){}; SegmentTree(F f,T ti):f(f),ti(ti){} void init(int n_){ n=1; while(n<n_) n<<=1; dat.assign(n<<1,ti); } void build(const vector<T> &v){ int n_=v.size(); init(n_); for(int i=0;i<n_;i++) dat[n+i]=v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } void set_val(int k,T x){ dat[k+=n]=x; while(k>>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } //[a,b) T query(int a,int b){ T vl=ti,vr=ti; for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,dat[l++]); if(r&1) vr=f(dat[--r],vr); } return f(vl,vr); } T operator[](const int &k) const {return dat[k + n];} }; int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N,Q;cin>>N>>Q; using hoge=tuple<ll,ll,ll,ll>; auto f=[](hoge a,hoge b){ ll asum,amax,al,ar; ll bsum,bmax,bl,br; tie(asum,amax,al,ar)=a; tie(bsum,bmax,bl,br)=b; ll csum,cmax,cl,cr; csum = asum+bsum; cmax = max({amax,bmax,ar+bl}); cl = max(al,asum+bl); cr = max(ar+bsum,br); return make_tuple(csum,cmax,cl,cr); }; SegmentTree<hoge> seg(f,make_tuple(0,-INF,-INF,-INF)); seg.init(N); vll a(N); for(ll i=0;i<N;i++){ cin>>a[i]; seg.set_val(i,make_tuple(a[i],a[i],a[i],a[i])); } for(ll q=0;q<Q;q++){ string op;cin>>op; if(op[0]=='s'){ ll i,x;cin>>i>>x;i--; seg.set_val(i,make_tuple(x,x,x,x)); a[i]=x; }else{ ll l1,l2,r1,r2;cin>>l1>>l2>>r1>>r2; l1--;l2--;r1--;r2--; ll ans=0; if(l2<r1){ hoge l=seg.query(l1,l2+1); hoge m=seg.query(l2+1,r1); hoge r=seg.query(r1,r2+1); ans = get<3>(l)+get<0>(m)+get<2>(r); }else if(r1<=l1){ if(l2<=r2){ hoge m=seg.query(l1,l2+1); hoge r=seg.query(l2,r2+1); ans = max(get<1>(m),get<3>(m)+get<2>(r)-a[l2]); }else{ hoge m=seg.query(l1,r2+1); ans = get<1>(m); } }else{ if(r2<=l2){ hoge l=seg.query(l1,r1+1); hoge m=seg.query(r1,r2+1); ans = max(get<1>(m),get<3>(l)+get<2>(m)-a[r1]); }else{ hoge l=seg.query(l1,r1+1); hoge m=seg.query(r1,l2+1); hoge r=seg.query(l2,r2+1); ans = get<1>(m); ans = max(ans,get<3>(l)+get<2>(m)-a[r1]); ans = max(ans,get<3>(m)+get<2>(r)-a[l2]); ans = max(ans,get<3>(l)+get<0>(m)+get<2>(r)-a[r1]-a[l2]); } } cout<<ans<<endl; } } return 0; }