結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | rickytheta |
提出日時 | 2018-12-11 23:30:59 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 384 ms / 3,000 ms |
コード長 | 3,463 bytes |
コンパイル時間 | 1,290 ms |
コンパイル使用メモリ | 164,100 KB |
実行使用メモリ | 13,688 KB |
最終ジャッジ日時 | 2024-09-24 08:49:21 |
合計ジャッジ時間 | 10,837 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
11,724 KB |
testcase_01 | AC | 5 ms
11,600 KB |
testcase_02 | AC | 33 ms
10,588 KB |
testcase_03 | AC | 123 ms
12,984 KB |
testcase_04 | AC | 164 ms
11,852 KB |
testcase_05 | AC | 277 ms
13,160 KB |
testcase_06 | AC | 75 ms
10,980 KB |
testcase_07 | AC | 167 ms
13,344 KB |
testcase_08 | AC | 214 ms
11,916 KB |
testcase_09 | AC | 60 ms
13,452 KB |
testcase_10 | AC | 121 ms
11,956 KB |
testcase_11 | AC | 213 ms
13,396 KB |
testcase_12 | AC | 289 ms
13,484 KB |
testcase_13 | AC | 292 ms
13,528 KB |
testcase_14 | AC | 295 ms
13,440 KB |
testcase_15 | AC | 288 ms
13,348 KB |
testcase_16 | AC | 291 ms
13,688 KB |
testcase_17 | AC | 384 ms
13,380 KB |
testcase_18 | AC | 207 ms
13,280 KB |
testcase_19 | AC | 341 ms
13,424 KB |
testcase_20 | AC | 337 ms
13,384 KB |
testcase_21 | AC | 332 ms
13,340 KB |
testcase_22 | AC | 339 ms
13,592 KB |
testcase_23 | AC | 334 ms
13,600 KB |
testcase_24 | AC | 332 ms
13,376 KB |
testcase_25 | AC | 78 ms
11,208 KB |
testcase_26 | AC | 190 ms
13,520 KB |
testcase_27 | AC | 171 ms
13,388 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:85:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 85 | scanf("%d%d",&n,&q); | ~~~~~^~~~~~~~~~~~~~ main.cpp:86:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 86 | REP(i,n)scanf("%lld",a+i); | ~~~~~^~~~~~~~~~~~ main.cpp:107:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 107 | scanf("%s",buf); | ~~~~~^~~~~~~~~~ main.cpp:111:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 111 | scanf("%d%d",&i,&x); --i; | ~~~~~^~~~~~~~~~~~~~ main.cpp:118:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 118 | scanf("%d%d%d%d",&l1,&l2,&r1,&r2); --l1; --l2; --r1; --r2; | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) for(int i=0;i<(int)(n);i++) #define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--) const ll INF = 1ll<<60; int n,q; ll a[125252]; ll sum[125252]; // segment tree const int N = 1<<17; ll datMin[2*N], datMax[2*N]; // range min/max ll datVal[2*N]; // (max. dat[j]-dat[i] s.t. l<=i<j<=r) bool lazyFlag[2*N]; ll lazyVal[2*N]; void push(int k){ if(!lazyFlag[k])return; datMin[k] += lazyVal[k]; datMax[k] += lazyVal[k]; if(k<N-1){ lazyFlag[2*k+1] = lazyFlag[2*k+2] = true; lazyVal[2*k+1] += lazyVal[k]; lazyVal[2*k+2] += lazyVal[k]; } lazyFlag[k] = false; lazyVal[k] = 0; } void queryAdd(int l, int r, ll v, int a, int b, int k){ push(k); if(r<=a || b<=l)return; if(l<=a && b<=r){ lazyFlag[k] = true; lazyVal[k] += v; push(k); return; } int m = (a+b)/2; queryAdd(l,r,v,a,m,2*k+1); queryAdd(l,r,v,m,b,2*k+2); datMin[k] = min(datMin[2*k+1], datMin[2*k+2]); datMax[k] = max(datMax[2*k+1], datMax[2*k+2]); datVal[k] = max(datVal[2*k+1], datVal[2*k+2]); datVal[k] = max(datVal[k], datMax[2*k+2] - datMin[2*k+1]); } void queryAdd(int l, int r, ll v){ queryAdd(l,r,v,0,N,0); } // <<min, max>, val> pair<pair<ll,ll>,ll> queryGet(int l, int r, int a, int b, int k){ push(k); if(r<=a || b<=l)return make_pair(make_pair(INF, -INF), -INF); if(l<=a && b<=r)return make_pair(make_pair(datMin[k], datMax[k]), datVal[k]); int m = (a+b)/2; pair<pair<ll,ll>,ll> lft, rgt; lft = queryGet(l,r,a,m,2*k+1); rgt = queryGet(l,r,m,b,2*k+2); ll mn = min(lft.first.first, rgt.first.first); ll mx = max(lft.first.second,rgt.first.second); ll vl = max(lft.second, rgt.second); vl = max(vl, rgt.first.second - lft.first.first); return make_pair(make_pair(mn,mx),vl); } ll queryMin(int l, int r){ return queryGet(l,r,0,N,0).first.first; } ll queryMax(int l, int r){ return queryGet(l,r,0,N,0).first.second; } ll queryVal(int l, int r){ return queryGet(l,r,0,N,0).second; } ll f1(int l1, int l2, int r1, int r2){ assert(l2<=r1); return queryMax(r1+1, r2+2) - queryMin(l1, l2+1); } int main(){ // input scanf("%d%d",&n,&q); REP(i,n)scanf("%lld",a+i); // construct segment tree REP(i,n)sum[i+1] = sum[i]+a[i]; REP(i,n+1){ datMin[i+N-1] = datMax[i+N-1] = sum[i]; datVal[i+N-1] = -INF; } FOR(i,n+1,N){ datMin[i+N-1] = INF; datMax[i+N-1] = -INF; datVal[i+N-1] = -INF; } FORR(i,0,N-1){ datMin[i] = min(datMin[2*i+1], datMin[2*i+2]); datMax[i] = max(datMax[2*i+1], datMax[2*i+2]); datVal[i] = max(datVal[2*i+1], datVal[2*i+2]); datVal[i] = max(datVal[i], datMax[2*i+2] - datMin[2*i+1]); } // query while(q--){ char buf[5]; scanf("%s",buf); if(buf[0]=='s'){ // set i x int i,x; scanf("%d%d",&i,&x); --i; ll diff = x - a[i]; a[i] = x; queryAdd(i+1, n+1, diff); }else{ // max l1 l2 r1 r2 int l1,l2,r1,r2; scanf("%d%d%d%d",&l1,&l2,&r1,&r2); --l1; --l2; --r1; --r2; r1 = max(r1, l1); l2 = min(l2, r2); assert(l1<=r1 && l2<=r2); ll ans = -INF; if(l2<=r1){ ans = f1(l1, l2, r1, r2); }else{ ans = max(ans, f1(l1, l2, l2, r2)); ans = max(ans, f1(l1, r1, r1, r2)); ans = max(ans, queryVal(r1, l2+1)); } printf("%lld\n",ans); } } return 0; }