結果

問題 No.776 A Simple RMQ Problem
コンテスト
ユーザー kriii
提出日時 2018-12-23 00:19:46
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,671 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 491 ms
コンパイル使用メモリ 34,688 KB
実行使用メモリ 23,680 KB
最終ジャッジ日時 2024-09-25 10:19:34
合計ジャッジ時間 6,007 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 #
raw source code 

#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