結果

問題 No.776 A Simple RMQ Problem
ユーザー hashiryohashiryo
提出日時 2019-06-04 13:38:11
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 301 ms / 3,000 ms
コード長 3,217 bytes
コンパイル時間 1,999 ms
コンパイル使用メモリ 176,704 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2023-10-17 23:42:48
合計ジャッジ時間 9,258 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 25 ms
5,628 KB
testcase_03 AC 93 ms
12,024 KB
testcase_04 AC 118 ms
5,628 KB
testcase_05 AC 193 ms
12,024 KB
testcase_06 AC 54 ms
7,672 KB
testcase_07 AC 125 ms
12,024 KB
testcase_08 AC 152 ms
7,672 KB
testcase_09 AC 52 ms
12,288 KB
testcase_10 AC 89 ms
7,672 KB
testcase_11 AC 158 ms
12,288 KB
testcase_12 AC 201 ms
12,288 KB
testcase_13 AC 205 ms
12,288 KB
testcase_14 AC 204 ms
12,288 KB
testcase_15 AC 203 ms
12,288 KB
testcase_16 AC 200 ms
12,288 KB
testcase_17 AC 301 ms
12,288 KB
testcase_18 AC 128 ms
12,288 KB
testcase_19 AC 254 ms
12,288 KB
testcase_20 AC 251 ms
12,288 KB
testcase_21 AC 250 ms
12,288 KB
testcase_22 AC 252 ms
12,288 KB
testcase_23 AC 248 ms
12,288 KB
testcase_24 AC 247 ms
12,288 KB
testcase_25 AC 51 ms
4,348 KB
testcase_26 AC 125 ms
12,288 KB
testcase_27 AC 103 ms
12,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long RmaxsumQ::T = 0; (RmaxsumQ::T) < (n); ++ (RmaxsumQ::T)) cerr << #x << "[" << RmaxsumQ::T << "]: " << x[RmaxsumQ::T] << '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll> Pll;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

template <typename M>
struct SegmentTree{
    using T = typename M::T;
    int n;
    vector<T> dat;
    SegmentTree(){}
    SegmentTree(int n_){init(n_);}
    SegmentTree(const vector<T> &v){build(v);}
    void init(int n_){
        n=1;
        while(n<n_) n<<=1;
        dat.assign(n<<1,M::ti());
    }
    void build(const vector<T> &v){
        int n_=v.size();
        init(n_);
        for(int i=0;i<n_;i++) dat[n+i]=v[i];
        for(int i=n-1;i;i--)
            dat[i]=M::f(dat[(i<<1)|0],dat[(i<<1)|1]);
    }
    void set_val(int k,T x){
        dat[k+=n]=x;
        while(k>>=1)
            dat[k]=M::f(dat[(k<<1)|0],dat[(k<<1)|1]);
    }
    //[a,b)
    T query(int a,int b,int k=1,int l=0,int r=-1){
        if(r<0)r=n;
        if(r<=a||b<=l) return M::ti();
        if(a<=l&&r<=b) return dat[k];
        T vl=query(a,b,k*2,l,(l+r)/2);
        T vr=query(a,b,k*2+1,(l+r)/2,r);
        return M::f(vl,vr);
    }
    T operator[](const int &k) const {return dat[k + n];}
};

struct RmaxsumQ{
    struct T{
      ll sum,max,l,r;
      T(){}
      T(ll a,ll b,ll c,ll d):sum(a),max(b),l(c),r(d){}
    };
    static T ti(){return T(0,-INF,-INF,-INF);}
    static T f(const T& a, const T & b){
        T ret;
        ret.sum = a.sum+b.sum;
        ret.max = max({a.max,b.max,a.r+b.l});
        ret.l = max(a.l,a.sum+b.l);
        ret.r = max(a.r+b.sum,b.r);
        return ret;
    }
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N,Q;cin>>N>>Q;
  SegmentTree<RmaxsumQ> seg(N);
  vll a(N);
  for(ll i=0;i<N;i++){
    cin>>a[i];
    seg.set_val(i,{a[i],a[i],a[i],a[i]});
  }
  for(ll q=0;q<Q;q++){
    string op;cin>>op;
    if(op[0]=='s'){
      ll i,x;cin>>i>>x;i--;
      seg.set_val(i,{x,x,x,x});
      a[i]=x;
    }else{
      ll l1,l2,r1,r2;cin>>l1>>l2>>r1>>r2;
      l1--;l2--;r1--;r2--;
      ll ans=0;
      if(l2<r1){
        RmaxsumQ::T l=seg.query(l1,l2+1);
        RmaxsumQ::T m=seg.query(l2+1,r1);
        RmaxsumQ::T r=seg.query(r1,r2+1);
        ans = l.r+m.sum+r.l;
      }else if(r1<=l1){
        if(l2<=r2){
          RmaxsumQ::T m=seg.query(l1,l2+1);
          RmaxsumQ::T r=seg.query(l2,r2+1);
          ans = max(m.max,m.r+r.l-a[l2]);
        }else{
          RmaxsumQ::T m=seg.query(l1,r2+1);
          ans = m.max;
        }
      }else{
        if(r2<=l2){
          RmaxsumQ::T l=seg.query(l1,r1+1);
          RmaxsumQ::T m=seg.query(r1,r2+1);
          ans = max(m.max,l.r+m.l-a[r1]);
        }else{
          RmaxsumQ::T l=seg.query(l1,r1+1);
          RmaxsumQ::T m=seg.query(r1,l2+1);
          RmaxsumQ::T r=seg.query(l2,r2+1);
          ans = m.max;
          ans = max(ans,l.r+m.l-a[r1]);
          ans = max(ans,m.r+r.l-a[l2]);
          ans = max(ans,l.r+m.sum+r.l-a[r1]-a[l2]);
        }
      }
      cout<<ans<<endl;
    }
  }
  return 0;
}
0