結果

問題 No.776 A Simple RMQ Problem
コンテスト
ユーザー rickytheta
提出日時 2018-12-11 23:30:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 384 ms / 3,000 ms
コード長 3,463 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,290 ms
コンパイル使用メモリ 164,100 KB
実行使用メモリ 13,688 KB
最終ジャッジ日時 2024-09-24 08:49:21
合計ジャッジ時間 10,837 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 #
raw source code 

#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