結果

問題 No.855 ヘビの日光浴
ユーザー QCFiumQCFium
提出日時 2019-07-10 11:39:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 156 ms / 3,153 ms
コード長 3,429 bytes
コンパイル時間 2,672 ms
コンパイル使用メモリ 186,388 KB
実行使用メモリ 16,080 KB
最終ジャッジ日時 2023-07-25 01:45:27
合計ジャッジ時間 9,428 ms
ジャッジサーバーID
(参考情報)
judge13 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 1 ms
4,384 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 1 ms
4,376 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 1 ms
4,384 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 2 ms
4,380 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 1 ms
4,380 KB
testcase_33 AC 2 ms
4,380 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 2 ms
4,376 KB
testcase_36 AC 1 ms
4,380 KB
testcase_37 AC 2 ms
4,380 KB
testcase_38 AC 2 ms
4,380 KB
testcase_39 AC 2 ms
4,376 KB
testcase_40 AC 2 ms
4,380 KB
testcase_41 AC 2 ms
4,384 KB
testcase_42 AC 2 ms
4,380 KB
testcase_43 AC 1 ms
4,376 KB
testcase_44 AC 2 ms
4,380 KB
testcase_45 AC 2 ms
4,380 KB
testcase_46 AC 1 ms
4,380 KB
testcase_47 AC 2 ms
4,380 KB
testcase_48 AC 2 ms
4,384 KB
testcase_49 AC 1 ms
4,380 KB
testcase_50 AC 2 ms
4,380 KB
testcase_51 AC 2 ms
4,376 KB
testcase_52 AC 1 ms
4,380 KB
testcase_53 AC 1 ms
4,376 KB
testcase_54 AC 1 ms
4,380 KB
testcase_55 AC 2 ms
4,376 KB
testcase_56 AC 1 ms
4,380 KB
testcase_57 AC 1 ms
4,376 KB
testcase_58 AC 2 ms
4,376 KB
testcase_59 AC 2 ms
4,380 KB
testcase_60 AC 1 ms
4,380 KB
testcase_61 AC 1 ms
4,384 KB
testcase_62 AC 1 ms
4,380 KB
testcase_63 AC 1 ms
4,380 KB
testcase_64 AC 1 ms
4,376 KB
testcase_65 AC 1 ms
4,380 KB
testcase_66 AC 2 ms
4,380 KB
testcase_67 AC 1 ms
4,376 KB
testcase_68 AC 1 ms
4,380 KB
testcase_69 AC 1 ms
4,380 KB
testcase_70 AC 1 ms
4,380 KB
testcase_71 AC 1 ms
4,376 KB
testcase_72 AC 2 ms
4,380 KB
testcase_73 AC 45 ms
8,020 KB
testcase_74 AC 45 ms
8,148 KB
testcase_75 AC 25 ms
6,056 KB
testcase_76 AC 98 ms
12,944 KB
testcase_77 AC 73 ms
10,164 KB
testcase_78 AC 122 ms
14,260 KB
testcase_79 AC 6 ms
4,380 KB
testcase_80 AC 7 ms
4,384 KB
testcase_81 AC 141 ms
15,800 KB
testcase_82 AC 145 ms
15,948 KB
testcase_83 AC 148 ms
15,904 KB
testcase_84 AC 150 ms
15,968 KB
testcase_85 AC 146 ms
15,928 KB
testcase_86 AC 156 ms
15,956 KB
testcase_87 AC 152 ms
16,080 KB
testcase_88 AC 149 ms
16,028 KB
testcase_89 AC 150 ms
16,020 KB
testcase_90 AC 149 ms
15,908 KB
testcase_91 AC 146 ms
15,908 KB
testcase_92 AC 149 ms
15,928 KB
testcase_93 AC 2 ms
4,504 KB
testcase_94 AC 88 ms
15,968 KB
権限があれば一括ダウンロードができます

ソースコード

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;
			int64_t 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;
			int64_t 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