結果

問題 No.776 A Simple RMQ Problem
ユーザー rickythetarickytheta
提出日時 2018-12-11 23:30:59
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 364 ms / 3,000 ms
コード長 3,463 bytes
コンパイル時間 1,696 ms
コンパイル使用メモリ 163,656 KB
実行使用メモリ 13,704 KB
最終ジャッジ日時 2023-10-24 17:08:06
合計ジャッジ時間 10,713 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
11,584 KB
testcase_01 AC 4 ms
11,584 KB
testcase_02 AC 33 ms
12,184 KB
testcase_03 AC 117 ms
13,256 KB
testcase_04 AC 169 ms
12,280 KB
testcase_05 AC 262 ms
13,340 KB
testcase_06 AC 75 ms
12,396 KB
testcase_07 AC 162 ms
13,436 KB
testcase_08 AC 214 ms
12,492 KB
testcase_09 AC 59 ms
13,520 KB
testcase_10 AC 118 ms
12,588 KB
testcase_11 AC 207 ms
13,604 KB
testcase_12 AC 273 ms
13,704 KB
testcase_13 AC 274 ms
13,704 KB
testcase_14 AC 274 ms
13,704 KB
testcase_15 AC 272 ms
13,704 KB
testcase_16 AC 276 ms
13,704 KB
testcase_17 AC 364 ms
13,704 KB
testcase_18 AC 197 ms
13,704 KB
testcase_19 AC 324 ms
13,704 KB
testcase_20 AC 324 ms
13,704 KB
testcase_21 AC 319 ms
13,704 KB
testcase_22 AC 324 ms
13,704 KB
testcase_23 AC 319 ms
13,704 KB
testcase_24 AC 316 ms
13,704 KB
testcase_25 AC 77 ms
11,580 KB
testcase_26 AC 176 ms
13,704 KB
testcase_27 AC 161 ms
13,704 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;
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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;
}
0