結果

問題 No.776 A Simple RMQ Problem
ユーザー chocoruskchocorusk
提出日時 2018-12-23 09:35:03
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 754 ms / 3,000 ms
コード長 3,202 bytes
コンパイル時間 1,220 ms
コンパイル使用メモリ 88,772 KB
実行使用メモリ 13,544 KB
最終ジャッジ日時 2023-10-26 02:25:56
合計ジャッジ時間 15,596 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
12,508 KB
testcase_01 AC 4 ms
12,508 KB
testcase_02 AC 61 ms
12,700 KB
testcase_03 AC 244 ms
13,476 KB
testcase_04 AC 304 ms
12,736 KB
testcase_05 AC 541 ms
13,512 KB
testcase_06 AC 141 ms
12,772 KB
testcase_07 AC 321 ms
13,544 KB
testcase_08 AC 423 ms
12,808 KB
testcase_09 AC 123 ms
13,544 KB
testcase_10 AC 224 ms
12,840 KB
testcase_11 AC 428 ms
13,544 KB
testcase_12 AC 537 ms
13,544 KB
testcase_13 AC 552 ms
13,544 KB
testcase_14 AC 539 ms
13,544 KB
testcase_15 AC 550 ms
13,544 KB
testcase_16 AC 559 ms
13,544 KB
testcase_17 AC 754 ms
13,544 KB
testcase_18 AC 383 ms
13,544 KB
testcase_19 AC 649 ms
13,544 KB
testcase_20 AC 671 ms
13,544 KB
testcase_21 AC 644 ms
13,544 KB
testcase_22 AC 672 ms
13,544 KB
testcase_23 AC 648 ms
13,544 KB
testcase_24 AC 639 ms
13,544 KB
testcase_25 AC 109 ms
12,508 KB
testcase_26 AC 335 ms
13,544 KB
testcase_27 AC 289 ms
13,544 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
    
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
    
const int MAX_N=1<<17;
 
const ll INF=1e18;
     
ll mn[2*MAX_N-1], mx[2*MAX_N-1], md[2*MAX_N-1], part[2*MAX_N-1];
bool mada[2*MAX_N-1];
int m;
ll s[100001];
void init(int n){
    m=1;
    while(m<n) m*=2;
	for(int i=m-1; i<m-1+n; i++){
		mn[i]=s[i-m+1], mx[i]=s[i-m+1], md[i]=-INF;
	}
	for(int i=m-1+n; i<2*m-1; i++){
		mn[i]=INF, mx[i]=-INF, md[i]=-INF;
	}
	for(int k=m-2; k>=0; k--){
		mn[k]=min(mn[2*k+1], mn[2*k+2]);
		mx[k]=max(mx[2*k+1], mx[2*k+2]);
		md[k]=max({mx[2*k+2]-mn[2*k+1], md[2*k+1], md[2*k+2]});
    }
}
   
void eval(int k, int l, int r){
    if(mada[k]){
        mn[k]+=part[k];
		mx[k]+=part[k];
        if(k<m-1){
            part[2*k+1]+=part[k];
            part[2*k+2]+=part[k];
          mada[2*k+1]=1; mada[2*k+2]=1;
        }
        mada[k]=0;
      part[k]=0;
    }
}
     
void add(int a, int b, ll x, int k, int l, int r){
    eval(k, l, r);
    if(r<=a || b<=l) return;
    if(a<=l && r<=b){
        part[k]=x;
      mada[k]=1;
        eval(k, l, r);
    }else{
        add(a, b, x, k*2+1, l, (l+r)/2);
        add(a, b, x, k*2+2, (l+r)/2, r);
        mn[k]=min(mn[2*k+1], mn[2*k+2]);
		mx[k]=max(mx[2*k+1], mx[2*k+2]);
		md[k]=max({mx[2*k+2]-mn[2*k+1], md[2*k+1], md[2*k+2]});
    }
}
     
ll findmn(int a, int b, int k, int l, int r){
    eval(k, l, r);
    if(b<=l || r<=a){
        return INF;
    }
    if(a<=l && r<=b){
        return mn[k];
    }else{
        return min(findmn(a, b, 2*k+1, l, (l+r)/2), findmn(a, b, 2*k+2, (l+r)/2, r));
    }
}
    
ll findmx(int a, int b, int k, int l, int r){
    eval(k, l, r);
    if(b<=l || r<=a){
        return -INF;
    }
    if(a<=l && r<=b){
        return mx[k];
    }else{
        return max(findmx(a, b, 2*k+1, l, (l+r)/2), findmx(a, b, 2*k+2, (l+r)/2, r));
    }
}
ll findmd(int a, int b, int k, int l, int r){
    eval(k, l, r);
    if(b<=l || r<=a){
        return -INF;
    }
    if(a<=l && r<=b){
        return md[k];
    }else{
		return max({findmd(a, b, 2*k+1, l, (l+r)/2), findmd(a, b, 2*k+2, (l+r)/2, r), findmx(a, b, 2*k+2, (l+r)/2, r)-findmn(a, b, 2*k+1, l, (l+r)/2)});
    }
}
int main()
{
    int n, q;
    cin>>n>>q;
	ll a[100001];
	for(int i=1; i<=n; i++){
		cin>>a[i]; s[i]=s[i-1]+a[i];
	}
    init(n+1);
    for(int i=0; i<q; i++){
        string t;
		cin>>t;
		if(t=="set"){
			int i; ll x; cin>>i>>x;
			ll d=x-a[i];
			add(i, n+1, d, 0, 0, m);
			a[i]=x;
		}else{
			int l1, l2, r1, r2;
			cin>>l1>>l2>>r1>>r2;
			l1--; l2--;
			if(l2<r1){
				cout<<findmx(r1, r2+1, 0, 0, m)-findmn(l1, l2+1, 0, 0, m)<<endl;
			}else{
				ll ans=-INF;
				if(l2<r2){
					ans=max(ans, findmx(l2+1, r2+1, 0, 0, m)-findmn(l1, l2+1, 0, 0, m));
				}
				if(l1<r1){
					ans=max(ans, findmx(r1, r2+1, 0, 0, m)-findmn(l1, r1, 0, 0, m));
				}
				l1=max(l1, r1), l2=min(l2, r2);
				ans=max(ans, findmd(l1, l2+1, 0, 0, m));
				cout<<ans<<endl;
			}
		}
	}
    return 0;
}
0