結果

問題 No.776 A Simple RMQ Problem
ユーザー kriiikriii
提出日時 2018-12-23 00:20:13
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 169 ms / 3,000 ms
コード長 1,695 bytes
コンパイル時間 393 ms
コンパイル使用メモリ 34,804 KB
実行使用メモリ 23,744 KB
最終ジャッジ日時 2024-09-25 10:19:39
合計ジャッジ時間 5,375 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
23,680 KB
testcase_01 AC 11 ms
23,552 KB
testcase_02 AC 24 ms
23,504 KB
testcase_03 AC 62 ms
23,640 KB
testcase_04 AC 77 ms
23,552 KB
testcase_05 AC 130 ms
23,552 KB
testcase_06 AC 46 ms
23,576 KB
testcase_07 AC 87 ms
23,560 KB
testcase_08 AC 103 ms
23,632 KB
testcase_09 AC 47 ms
23,552 KB
testcase_10 AC 65 ms
23,568 KB
testcase_11 AC 107 ms
23,532 KB
testcase_12 AC 133 ms
23,576 KB
testcase_13 AC 132 ms
23,680 KB
testcase_14 AC 133 ms
23,552 KB
testcase_15 AC 132 ms
23,744 KB
testcase_16 AC 133 ms
23,680 KB
testcase_17 AC 169 ms
23,552 KB
testcase_18 AC 102 ms
23,552 KB
testcase_19 AC 153 ms
23,680 KB
testcase_20 AC 152 ms
23,680 KB
testcase_21 AC 152 ms
23,552 KB
testcase_22 AC 152 ms
23,552 KB
testcase_23 AC 150 ms
23,552 KB
testcase_24 AC 148 ms
23,680 KB
testcase_25 AC 53 ms
23,552 KB
testcase_26 AC 105 ms
23,552 KB
testcase_27 AC 94 ms
23,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int Z = 1<<18;

struct node{
	node(){sum = pr = sf = mx = 0; f = 1;}
	node(int a){sum = pr = sf = mx = a; f = 0;}
	long long sum, pr, sf, mx; bool f;
	node operator + (node t){
		if (f) return t;
		if (t.f) return (*this);
		node r; r.f = 0;
		r.sum = sum + t.sum;
		r.pr = pr;
		if (r.pr < sum + t.pr)
			r.pr = sum + t.pr;
		r.sf = t.sf;
		if (r.sf < sf + t.sum)
			r.sf = sf + t.sum;
		r.mx = sf + t.pr;
		if (r.mx < mx)
			r.mx = mx;
		if (r.mx < t.mx)
			r.mx = t.mx;
		return r;
	}
}IT[Z*2];

void in(int x, int a)
{
	x += Z; IT[x] = a; x /= 2;
	while (x){
		IT[x] = IT[x*2] + IT[x*2+1];
		x /= 2;
	}
}

node pop(int x, int y)
{
	node l, r;
	x += Z; y += Z;
	while (x < y){
		if (x & 1) l = l + IT[x++];
		if (~y & 1) r = IT[y--] + r;
		x /= 2; y /= 2;
	} if (x == y) l = l + IT[x];
	return l + r;
}

int main()
{
	int N,Q;
	scanf ("%d %d",&N,&Q);
	for (int i=1,a;i<=N;i++) scanf ("%d",&a), IT[i+Z] = a;
	for (int i=Z-1;i>=1;i--) IT[i] = IT[i*2] + IT[i*2+1];

	while (Q--){
		char op[6]; scanf ("%s",op);

		if (op[0] == 'm'){
			int l1,l2,r1,r2;
			scanf ("%d %d %d %d",&l1,&l2,&r1,&r2);
			if (r1 < l1) r1 = l1;
			if (r2 < l2) l2 = r2;
			auto p = pop(l1,l2);
			auto r = pop(r1,r2);
			long long ans;
			if (l2 < r1){
				auto q = pop(l2+1,r1-1);
				ans = p.sf + q.sum + r.pr;
			}
			else{
				auto q = pop(r1,l2);
				ans = q.mx;
				if (l1 < r1){
					auto pp = pop(l1,r1-1);
					if (ans < pp.sf + r.pr)
						ans = pp.sf + r.pr;
				}
				if (l2 < r2){
					auto rr = pop(l2+1,r2);
					if (ans < p.sf + rr.pr)
						ans = p.sf + rr.pr;
				}
			}
			printf ("%lld\n",ans);
		}
		else{
			int x,a; scanf ("%d %d",&x,&a);
			in(x,a);
		}
	}

	return 0;
}
0