結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
23,680 KB
testcase_01 AC 10 ms
23,552 KB
testcase_02 AC 26 ms
23,544 KB
testcase_03 AC 60 ms
23,600 KB
testcase_04 AC 75 ms
23,552 KB
testcase_05 AC 124 ms
23,552 KB
testcase_06 AC 40 ms
23,668 KB
testcase_07 AC 81 ms
23,680 KB
testcase_08 WA -
testcase_09 AC 43 ms
23,552 KB
testcase_10 WA -
testcase_11 AC 103 ms
23,552 KB
testcase_12 AC 134 ms
23,552 KB
testcase_13 AC 131 ms
23,552 KB
testcase_14 AC 132 ms
23,552 KB
testcase_15 AC 130 ms
23,552 KB
testcase_16 AC 133 ms
23,680 KB
testcase_17 AC 162 ms
23,680 KB
testcase_18 AC 103 ms
23,536 KB
testcase_19 AC 145 ms
23,680 KB
testcase_20 WA -
testcase_21 AC 148 ms
23,552 KB
testcase_22 WA -
testcase_23 AC 146 ms
23,612 KB
testcase_24 AC 145 ms
23,680 KB
testcase_25 AC 52 ms
23,680 KB
testcase_26 AC 103 ms
23,552 KB
testcase_27 AC 93 ms
23,552 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'node pop(int, int)':
main.cpp:40:17: warning: 'r.node::mx' may be used uninitialized [-Wmaybe-uninitialized]
   40 |         node l, r;
      |                 ^
main.cpp:40:17: warning: 'r.node::sf' may be used uninitialized [-Wmaybe-uninitialized]
In member function 'node node::operator+(node)',
    inlined from 'node pop(int, int)' at main.cpp:47:13:
main.cpp:20:27: warning: 'r.node::pr' may be used uninitialized [-Wmaybe-uninitialized]
   20 |                 r.mx = sf + t.pr;
      |                        ~~~^~~~~~
main.cpp: In function 'node pop(int, int)':
main.cpp:40:17: note: 'r.node::pr' was declared here
   40 |         node l, r;
      |                 ^
In member function 'node node::operator+(node)',
    inlined from 'node pop(int, int)' at main.cpp:47:13:
main.cpp:18:31: warning: 'r.node::sum' may be used uninitialized [-Wmaybe-uninitialized]
   18 |                 if (r.sf < sf + t.sum)
      |                            ~~~^~~~~~~
main.cpp: In function 'node pop(int, int)':
main.cpp:40:17: note: 'r.node::sum' was declared here
   40 |         node l, r;
      |                 ^

ソースコード

diff # 

#include <stdio.h>

const int Z = 1<<18;

struct node{
	node(){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