結果

問題 No.776 A Simple RMQ Problem
ユーザー rickythetarickytheta
提出日時 2018-12-12 13:01:52
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 434 ms / 3,000 ms
コード長 3,558 bytes
コンパイル時間 1,802 ms
コンパイル使用メモリ 162,824 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-25 03:32:51
合計ジャッジ時間 13,704 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,812 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 41 ms
6,940 KB
testcase_03 AC 158 ms
6,944 KB
testcase_04 AC 228 ms
6,944 KB
testcase_05 AC 372 ms
6,944 KB
testcase_06 AC 98 ms
6,940 KB
testcase_07 AC 226 ms
6,944 KB
testcase_08 AC 291 ms
6,944 KB
testcase_09 AC 76 ms
6,940 KB
testcase_10 AC 158 ms
6,948 KB
testcase_11 AC 294 ms
6,944 KB
testcase_12 AC 396 ms
6,944 KB
testcase_13 AC 395 ms
6,940 KB
testcase_14 AC 394 ms
6,940 KB
testcase_15 AC 388 ms
6,944 KB
testcase_16 AC 393 ms
6,940 KB
testcase_17 AC 405 ms
6,940 KB
testcase_18 AC 384 ms
6,940 KB
testcase_19 AC 388 ms
6,940 KB
testcase_20 AC 388 ms
6,948 KB
testcase_21 AC 390 ms
6,944 KB
testcase_22 AC 355 ms
6,940 KB
testcase_23 AC 398 ms
6,940 KB
testcase_24 AC 434 ms
6,944 KB
testcase_25 AC 193 ms
6,944 KB
testcase_26 AC 369 ms
6,940 KB
testcase_27 AC 364 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:125:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  125 |   scanf("%d%d",&n,&q);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:126:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  126 |   REP(i,n)scanf("%d",a+i);
      |           ~~~~~^~~~~~~~~~
main.cpp:134:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  134 |     scanf("%s",buf);
      |     ~~~~~^~~~~~~~~~
main.cpp:138:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  138 |       scanf("%d%d",&i,&x); --i;
      |       ~~~~~^~~~~~~~~~~~~~
main.cpp:145:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  145 |       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--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

const ll INF = 1ll<<60;

int n,q;
int a[125252];
ll sum[125252];
// sqrt decomposition
const int N = 100025;     // max n
const int B = 252;        // bucket size
const int C = (N+B-1)/B;  // max bucket count
ll bucketMax[C], bucketMin[C], bucketVal[C];
ll lazyVal[C];

// O(n) calc for max_{l<r}(sum[r]-sum[l])
ll tmp[2*B+2*C+10];
ll calcMax[2*B+2*C+10];
ll calcVal(int n, ll *arr){
  calcMax[n] = -INF;
  FORR(i,0,n)calcMax[i] = max(calcMax[i+1], arr[i]);
  ll ret = -INF;
  ll mn = INF;
  REP(i,n){
    CHMIN(mn, arr[i]);
    CHMAX(ret, calcMax[i+1] - mn);
  }
  return ret;
}
// bucket operation
void calcBucket(int id){
  bucketMax[id] = -INF;
  bucketMin[id] =  INF;
  lazyVal[id] = 0;
  REP(i,B){
    CHMAX(bucketMax[id], sum[id*B+i]);
    CHMIN(bucketMin[id], sum[id*B+i]);
  }
  bucketVal[id] = calcVal(B, sum+id*B);
}
void addToBucket(int id, ll v){
  bucketMax[id] += v;
  bucketMin[id] += v;
  lazyVal[id] += v;
}
void push(int id){
  if(lazyVal[id]==0)return;
  REP(i,B)sum[id*B+i] += lazyVal[id];
  lazyVal[id] = 0;
}
void queryAdd(int l, int r, ll v){
  int it = l;
  // left bucket
  push(it/B);
  while(it<r && it%B>0)sum[it++] += v;
  calcBucket(l/B);
  // between bucket
  while(it+B<=r){addToBucket(it/B, v); it+=B;}
  // right bucket
  push(it/B);
  while(it<r)sum[it++] += v;
  calcBucket(r/B);
}
ll queryMax(int l, int r){
  ll ret = -INF;
  int it = l;
  // left bucket
  push(it/B);
  while(it<r && it%B>0)CHMAX(ret, sum[it++]);
  // between bucket
  while(it+B<=r){CHMAX(ret, bucketMax[it/B]); it+=B;}
  // right bucket
  push(it/B);
  while(it<r)CHMAX(ret, sum[it++]);
  return ret;
}
ll queryMin(int l, int r){
  ll ret = INF;
  int it = l;
  // left bucket
  push(it/B);
  while(it<r && it%B>0)CHMIN(ret, sum[it++]);
  // between bucket
  while(it+B<=r){CHMIN(ret, bucketMin[it/B]); it+=B;}
  // right bucket
  push(it/B);
  while(it<r)CHMIN(ret, sum[it++]);
  return ret;
}
ll queryVal(int l, int r){
  ll ret = -INF;
  int it = l;
  int m = 0;
  // left bucket
  push(it/B);
  while(it<r && it%B>0)tmp[m++] = sum[it++];
  // between bucket
  while(it+B<=r){
    CHMAX(ret, bucketVal[it/B]);
    tmp[m++] = bucketMax[it/B];
    tmp[m++] = bucketMin[it/B];
    it += B;
  }
  // right bucket
  push(it/B);
  while(it<r)tmp[m++] = sum[it++];
  CHMAX(ret, calcVal(m, tmp));
  return ret;
}

ll f1(int l1, int l2, int r1, int r2){
  return queryMax(r1+1, r2+2) - queryMin(l1, l2+1);
}

int main(){
  // input
  scanf("%d%d",&n,&q);
  REP(i,n)scanf("%d",a+i);
  // construct sqrt decomposition
  sum[0] = 0;
  REP(i,n)sum[i+1] = sum[i]+a[i];
  REP(i,C)calcBucket(i);
  // 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);
      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