Submission #1865011

---

Source Code Expand

#include<cstdio>

//segment tree size==2^0+...+2^18==524287
long long a[200000], st[524287], d[524287];

long long max(long long a, long long b){
	return a < b ? b : a;
}

//O(n+qlogn)...stを作るのにdpの2倍ほど時間がかかる
int main() {
	
	int n, q, i, j, p;
	long long x, y;
	long long suma=0;

	scanf("%d%d", &n, &q);

	//start=segment treeの最下段の始まる位置=segment treeの最下段の長さ-1
	int start = 2;
	for (i = n - 2; i > 0; i = i / 2) {
		start = start * 2;
	}
	start--;
	
	//初期値の代入
	for (i = 0; i < 2 * n; i++) {
		scanf("%lld", &a[i]);
		suma += a[i];
	}
	scanf("%lld", &y);
	for (i = start; i < start + 2 * n - 2; i++) {
		scanf("%lld", &y);
		d[i] = y - a[i - start + 1];
	}
	scanf("%lld", &y);
	for (i = start + 2 * n - 2; i <= 2 * start; i++) {
		d[i] = -1000000000000000;
	}
	for (i = start; i <= start + 2 * n - 1; i++) {
		st[i] = 0;
	}

	//segment treeの作成
	for (i = start - 1; i >= 0; i--) {
		st[i] = max(st[2 * i + 1] + st[2 * i + 2], d[2 * i + 1] + d[2 * i + 2]);
		d[i] = max(st[2 * i + 1] + d[2 * i + 2], st[2 * i + 2] + d[2 * i + 1]);
	}
	
	for (i = 0; i < q; i++) {
		scanf("%d%lld%lld", &p, &x, &y);
		suma += x - a[p - 1];
		a[p - 1] = x;
		if (p != 1 && p != 2 * n) {
			j = start + p - 2;
			d[j] = y - x;
			do {
				j = (j - 1) / 2;
				st[j] = max(st[2 * j + 1] + st[2 * j + 2], d[2 * j + 1] + d[2 * j + 2]);
				d[j] = max(st[2 * j + 1] + d[2 * j + 2], st[2 * j + 2] + d[2 * j + 1]);
			} while (j > 0);
		}
		printf("%lld\n", suma + st[0]);
	}

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:17:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
                       ^
./Main.cpp:28:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
                       ^
./Main.cpp:31:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &y);
                   ^
./Main.cpp:33:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &y);
                    ^
./Main.cpp:36:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &y);
                   ^
./Main.cpp:51:34: warning: ignori...

Judge Result