#483209 (C++14) No.1099 Range Square Sum

• 問題: No.1099 Range Square Sum
• ユーザー: QCFium
• 提出日時: 2020-05-17 21:23:24
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 2,924 bytes
• コンパイル時間: 1,888 ms
• コンパイル使用メモリ: 175,504 KB
• 実行使用メモリ: 10,368 KB
• 最終ジャッジ日時: 2024-11-22 16:37:43
• 合計ジャッジ時間: 5,385 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-

ソースコード

#include <bits/stdc++.h>

/* strict input checker */

int read_int() {
	int c = getchar(), s = 0, res = 0;
	if (c == '-') s = 1, c = getchar();
	assert('0' <= c && c <= '9');
	if (s) assert(c != '0');
	res = c - '0';
	while (1) {
		c = getchar();
		if (c < '0' || c > '9') break;
		assert(res <= 200000000); // avoid overflow
		assert(res); // no leading-zero
		res = res * 10 + c - '0';
	}
	ungetc(c, stdin);
	return res;
}
void read_linebreak() {
	int c = getchar();
	if (c == '\r') c = getchar();
	assert(c == '\n');
}

#define INF 1000000000

struct SegTree {
	int n;
	std::vector<int> max;
	std::vector<int> min;
	std::vector<int> added;
	SegTree (const std::vector<int> &a) {
		for (n = 1; n < (int) a.size(); n <<= 1);
		added.resize(n << 1);
		min.resize(n << 1, INF);
		max.resize(n << 1, -INF);
		for (int i = 0; i < (int) a.size(); i++) max[i + n] = min[i + n] = a[i];
		for (int i = n; --i; ) fetch(i);
	}
	void flush(int i) {
		if (added[i]) {
			max[i] += added[i];
			min[i] += added[i];
			if (i < n) {
				added[i << 1] += added[i];
				added[i << 1 | 1] += added[i];
			}
			added[i] = 0;
		}
	}
	void fetch(int i) {
		max[i] = std::max(max[i << 1], max[i << 1 | 1]);
		min[i] = std::min(min[i << 1], min[i << 1 | 1]);
	}
	template<class T> void dive(int l, int r, int node, int node_l, int node_r, const T &func) {
		flush(node);
		if (r <= node_l || l >= node_r) return;
		if (l <= node_l && r >= node_r) func(node);
		else {
			int mid = node_l + ((node_r - node_l) >> 1);
			dive(l, r, node << 1, node_l, mid, func);
			dive(l, r, node << 1 | 1, mid, node_r, func);
			fetch(node);
		}
	}
	void add(int l, int r, int val) {
		dive(l, r, 1, 0, n, [&] (int node) { added[node] += val; flush(node); });
	}
	int64_t get_max(int l, int r) {
		int res = -INF;
		dive(l, r, 1, 0, n, [&] (int node) { res = std::max(res, max[node]); });
		return res;
	}
	int64_t get_min(int l, int r) {
		int res = INF;
		dive(l, r, 1, 0, n, [&] (int node) { res = std::max(res, min[node]); });
		return res;
	}
};

int main() {
	int n = read_int();
	read_linebreak();
	
	assert(1 <= n && n <= 200000);
	
	std::vector<int> a(n);
	for (int i = 0; i < n; i++) {
		if (i) assert(getchar() == ' ');
		a[i] = read_int();
		assert(std::abs(a[i]) <= 1000000);
	}
	read_linebreak();
	
	int q = read_int();
	read_linebreak();
	
	assert(1 <= q && q <= 100000);
	
	bool r0 = false;
	SegTree tree(a);
	for (int i = 0; i < q; i++) {
		int t = read_int();
		assert(getchar() == ' ');
		int l = read_int();
		assert(getchar() == ' ');
		int r = read_int();
		
		assert(1 <= l && l <= r && r <= n);
		
		if (t == 1) {
			assert(getchar() == ' ');
			int val = read_int();
			assert(std::abs(val) <= 1000000);
			tree.add(l - 1, r, val);
		} else assert(t == 2), r0 = true;
		assert(tree.get_max(0, tree.n) <= 1000000);
		assert(tree.get_min(0, tree.n) >= -1000000);
		read_linebreak();
	}
	assert(r0);
	assert(getchar() == EOF);
	return 0;
}