結果

問題 No.855 ヘビの日光浴
ユーザー QCFiumQCFium
提出日時 2019-07-10 11:06:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 176 ms / 3,153 ms
コード長 3,421 bytes
コンパイル時間 1,783 ms
コンパイル使用メモリ 187,504 KB
実行使用メモリ 16,512 KB
最終ジャッジ日時 2024-10-01 20:41:54
合計ジャッジ時間 6,380 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct SegTree {
	std::vector<int> data;
	int n;
	SegTree(int _n) {
		for (n = 1; n < _n; n <<= 1);
		data.resize(2 * n);
	}
	void set(int i, int val) {
		data[i + n] = val;
		for (int cur = (i + n) >> 1; cur; cur >>= 1) data[cur] = std::max(data[cur << 1], data[cur << 1 | 1]);
	}
	int operator [] (int i) {
		return data[i + n];
	}
	// >= val
	int bin_search(int val, bool back) {
		if (data[1] < val) return back ? -1 : n;
		int cur = 1;
		if (back) {
			while (cur < n) {
				cur = cur << 1 | 1;
				if (data[cur] < val) cur--;
			}
		} else {
			while (cur < n) {
				cur <<= 1;
				if (data[cur] < val) cur++;
			}
		}
		return cur - n;
	}
};

int main() {
	int h = ri(), w = ri(), q = ri();
	std::set<int> xs, ys;
	std::vector<int> x(q), y(q), l(q);
	for (int i = 0; i < q; i++) {
		x[i] = ri();
		y[i] = ri();
		l[i] = ri();
		if (!x[i] || x[i] == w + 1) ys.insert(y[i]);
		else xs.insert(x[i]);
	}
	std::map<int, int> compx, compy;
	std::vector<int> decompx, decompy;
	int cntx = 0, cnty = 0;
	for (auto i : xs) {
		compx[i] = cntx++;
		decompx.push_back(i);
	}
	for (auto i : ys) {
		compy[i] = cnty++;
		decompy.push_back(i);
	}
	SegTree x1(cntx), x2(cntx);
	SegTree y1(cnty), y2(cnty);
	for (int i = 0; i < q; i++) {
		if (!x[i] || x[i] == w + 1) {
			// std::cerr << "extract x" << std::endl;
			int r0 = x1.bin_search(y[i], x[i] == w + 1);
			int r1 = x2.bin_search(h + 1 - y[i], x[i] == w + 1);
			if (r0 >= 0 && r0 < cntx) assert(r0 != r1);
			if (x[i] == w + 1) r0 = std::max(r0, r1);
			else r0 = std::min(r0, r1);
			// std::cerr << "r0:" << r0 << std::endl;
			SegTree &self = x[i] == w + 1 ? y2 : y1;
			SegTree &opp = x[i] == w + 1 ? y1 : y2;
			int new_len = self[compy[y[i]]] + l[i];
			// std::cerr << "new_len:" << new_len << std::endl;
			if (r0 >= 0 && r0 < cntx && (x[i] == w + 1 ? decompx[r0] + new_len > w : decompx[r0] <= new_len)) {
				// std::cerr << "cross collision" << std::endl;
				self.set(compy[y[i]], 0);
				if (r1 == r0) x2.set(r0, 0);
				else x1.set(r0, 0);
			} else if (opp[compy[y[i]]] + new_len > w) {
				// std::cerr << "direct collision" << std::endl;
				self.set(compy[y[i]], 0);
				opp.set(compy[y[i]], 0);
			} else self.set(compy[y[i]], new_len);
		} else {
			// std::cerr << "extract y" << std::endl;
			int r0 = y1.bin_search(x[i], y[i] == h + 1);
			int r1 = y2.bin_search(w + 1 - x[i], y[i] == h + 1);
			if (r0 >= 0 && r0 < cnty) assert(r0 != r1);
			if (y[i] == h + 1) r0 = std::max(r0, r1);
			else r0 = std::min(r0, r1);
			// std::cerr << "r0:" << r0 << std::endl;
			SegTree &self = y[i] == h + 1 ? x2 : x1;
			SegTree &opp = y[i] == h + 1 ? x1 : x2;
			int new_len = self[compx[x[i]]] + l[i];
			// std::cerr << "new_len:" << new_len << std::endl;
			if (r0 >= 0 && r0 < cnty && (y[i] == h + 1 ? decompy[r0] + new_len > h : decompy[r0] <= new_len)) {
				// std::cerr << "cross collision" << std::endl;
				self.set(compx[x[i]], 0);
				if (r1 == r0) y2.set(r0, 0);
				else y1.set(r0, 0);
			} else if (opp[compx[x[i]]] + new_len > h) {
				// std::cerr << "direct collision" << std::endl;
				self.set(compx[x[i]], 0);
				opp.set(compx[x[i]], 0);
			} else self.set(compx[x[i]], new_len);
		}
	}
	int64_t res = 0;
	for (int i = 0; i < cntx; i++) res += x1[i] + x2[i];
	for (int i = 0; i < cnty; i++) res += y1[i] + y2[i];
	std::cout << res << std::endl;
	return 0;
}
0