結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | chocorusk |
提出日時 | 2018-12-23 09:35:03 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 797 ms / 3,000 ms |
コード長 | 3,202 bytes |
コンパイル時間 | 974 ms |
コンパイル使用メモリ | 88,024 KB |
実行使用メモリ | 12,928 KB |
最終ジャッジ日時 | 2024-09-25 10:28:42 |
合計ジャッジ時間 | 14,791 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,248 KB |
testcase_02 | AC | 60 ms
6,400 KB |
testcase_03 | AC | 243 ms
12,288 KB |
testcase_04 | AC | 340 ms
6,400 KB |
testcase_05 | AC | 550 ms
12,416 KB |
testcase_06 | AC | 145 ms
7,936 KB |
testcase_07 | AC | 342 ms
12,672 KB |
testcase_08 | AC | 410 ms
8,320 KB |
testcase_09 | AC | 129 ms
12,800 KB |
testcase_10 | AC | 233 ms
8,448 KB |
testcase_11 | AC | 432 ms
12,800 KB |
testcase_12 | AC | 561 ms
12,800 KB |
testcase_13 | AC | 565 ms
12,800 KB |
testcase_14 | AC | 558 ms
12,928 KB |
testcase_15 | AC | 556 ms
12,928 KB |
testcase_16 | AC | 562 ms
12,800 KB |
testcase_17 | AC | 797 ms
12,928 KB |
testcase_18 | AC | 374 ms
12,928 KB |
testcase_19 | AC | 680 ms
12,928 KB |
testcase_20 | AC | 692 ms
12,800 KB |
testcase_21 | AC | 672 ms
12,800 KB |
testcase_22 | AC | 674 ms
12,928 KB |
testcase_23 | AC | 675 ms
12,928 KB |
testcase_24 | AC | 666 ms
12,800 KB |
testcase_25 | AC | 109 ms
5,376 KB |
testcase_26 | AC | 341 ms
12,928 KB |
testcase_27 | AC | 288 ms
12,672 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> using namespace std; typedef long long int ll; typedef pair<int, int> P; const int MAX_N=1<<17; const ll INF=1e18; ll mn[2*MAX_N-1], mx[2*MAX_N-1], md[2*MAX_N-1], part[2*MAX_N-1]; bool mada[2*MAX_N-1]; int m; ll s[100001]; void init(int n){ m=1; while(m<n) m*=2; for(int i=m-1; i<m-1+n; i++){ mn[i]=s[i-m+1], mx[i]=s[i-m+1], md[i]=-INF; } for(int i=m-1+n; i<2*m-1; i++){ mn[i]=INF, mx[i]=-INF, md[i]=-INF; } for(int k=m-2; k>=0; k--){ mn[k]=min(mn[2*k+1], mn[2*k+2]); mx[k]=max(mx[2*k+1], mx[2*k+2]); md[k]=max({mx[2*k+2]-mn[2*k+1], md[2*k+1], md[2*k+2]}); } } void eval(int k, int l, int r){ if(mada[k]){ mn[k]+=part[k]; mx[k]+=part[k]; if(k<m-1){ part[2*k+1]+=part[k]; part[2*k+2]+=part[k]; mada[2*k+1]=1; mada[2*k+2]=1; } mada[k]=0; part[k]=0; } } void add(int a, int b, ll x, int k, int l, int r){ eval(k, l, r); if(r<=a || b<=l) return; if(a<=l && r<=b){ part[k]=x; mada[k]=1; eval(k, l, r); }else{ add(a, b, x, k*2+1, l, (l+r)/2); add(a, b, x, k*2+2, (l+r)/2, r); mn[k]=min(mn[2*k+1], mn[2*k+2]); mx[k]=max(mx[2*k+1], mx[2*k+2]); md[k]=max({mx[2*k+2]-mn[2*k+1], md[2*k+1], md[2*k+2]}); } } ll findmn(int a, int b, int k, int l, int r){ eval(k, l, r); if(b<=l || r<=a){ return INF; } if(a<=l && r<=b){ return mn[k]; }else{ return min(findmn(a, b, 2*k+1, l, (l+r)/2), findmn(a, b, 2*k+2, (l+r)/2, r)); } } ll findmx(int a, int b, int k, int l, int r){ eval(k, l, r); if(b<=l || r<=a){ return -INF; } if(a<=l && r<=b){ return mx[k]; }else{ return max(findmx(a, b, 2*k+1, l, (l+r)/2), findmx(a, b, 2*k+2, (l+r)/2, r)); } } ll findmd(int a, int b, int k, int l, int r){ eval(k, l, r); if(b<=l || r<=a){ return -INF; } if(a<=l && r<=b){ return md[k]; }else{ return max({findmd(a, b, 2*k+1, l, (l+r)/2), findmd(a, b, 2*k+2, (l+r)/2, r), findmx(a, b, 2*k+2, (l+r)/2, r)-findmn(a, b, 2*k+1, l, (l+r)/2)}); } } int main() { int n, q; cin>>n>>q; ll a[100001]; for(int i=1; i<=n; i++){ cin>>a[i]; s[i]=s[i-1]+a[i]; } init(n+1); for(int i=0; i<q; i++){ string t; cin>>t; if(t=="set"){ int i; ll x; cin>>i>>x; ll d=x-a[i]; add(i, n+1, d, 0, 0, m); a[i]=x; }else{ int l1, l2, r1, r2; cin>>l1>>l2>>r1>>r2; l1--; l2--; if(l2<r1){ cout<<findmx(r1, r2+1, 0, 0, m)-findmn(l1, l2+1, 0, 0, m)<<endl; }else{ ll ans=-INF; if(l2<r2){ ans=max(ans, findmx(l2+1, r2+1, 0, 0, m)-findmn(l1, l2+1, 0, 0, m)); } if(l1<r1){ ans=max(ans, findmx(r1, r2+1, 0, 0, m)-findmn(l1, r1, 0, 0, m)); } l1=max(l1, r1), l2=min(l2, r2); ans=max(ans, findmd(l1, l2+1, 0, 0, m)); cout<<ans<<endl; } } } return 0; }