結果

問題 No.1099 Range Square Sum
コンテスト
ユーザー QCFium
提出日時 2020-05-17 21:23:24
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 20 RE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0