#358556 (C++14) No.855 ヘビの日光浴

提出ソース

結果

問題	No.855 ヘビの日光浴
ユーザー	QCFium
提出日時	2019-07-10 11:39:16
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	186 ms / 3,153 ms
コード長	3,429 bytes
コンパイル時間	2,083 ms
コンパイル使用メモリ	187,868 KB
実行使用メモリ	16,512 KB
最終ジャッジ日時	2024-10-01 20:43:19
合計ジャッジ時間	7,237 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	2 ms 6,820 KB
testcase_16	AC	2 ms 6,816 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	2 ms 6,820 KB
testcase_20	AC	2 ms 6,816 KB
testcase_21	AC	2 ms 6,820 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	2 ms 6,816 KB
testcase_24	AC	2 ms 6,820 KB
testcase_25	AC	2 ms 6,820 KB
testcase_26	AC	2 ms 6,820 KB
testcase_27	AC	2 ms 6,820 KB
testcase_28	AC	2 ms 6,816 KB
testcase_29	AC	2 ms 6,820 KB
testcase_30	AC	2 ms 6,820 KB
testcase_31	AC	2 ms 6,820 KB
testcase_32	AC	2 ms 6,824 KB
testcase_33	AC	2 ms 6,820 KB
testcase_34	AC	3 ms 6,820 KB
testcase_35	AC	2 ms 6,816 KB
testcase_36	AC	3 ms 6,824 KB
testcase_37	AC	2 ms 6,820 KB
testcase_38	AC	3 ms 6,816 KB
testcase_39	AC	2 ms 6,820 KB
testcase_40	AC	3 ms 6,816 KB
testcase_41	AC	2 ms 6,816 KB
testcase_42	AC	2 ms 6,816 KB
testcase_43	AC	2 ms 6,816 KB
testcase_44	AC	3 ms 6,820 KB
testcase_45	AC	2 ms 6,820 KB
testcase_46	AC	2 ms 6,816 KB
testcase_47	AC	2 ms 6,816 KB
testcase_48	AC	3 ms 6,816 KB
testcase_49	AC	2 ms 6,816 KB
testcase_50	AC	2 ms 6,816 KB
testcase_51	AC	2 ms 6,816 KB
testcase_52	AC	2 ms 6,816 KB
testcase_53	AC	2 ms 6,820 KB
testcase_54	AC	2 ms 6,820 KB
testcase_55	AC	1 ms 6,816 KB
testcase_56	AC	2 ms 6,816 KB
testcase_57	AC	2 ms 6,816 KB
testcase_58	AC	2 ms 6,816 KB
testcase_59	AC	2 ms 6,816 KB
testcase_60	AC	1 ms 6,816 KB
testcase_61	AC	2 ms 6,816 KB
testcase_62	AC	2 ms 6,820 KB
testcase_63	AC	2 ms 6,820 KB
testcase_64	AC	2 ms 6,820 KB
testcase_65	AC	2 ms 6,820 KB
testcase_66	AC	2 ms 6,816 KB
testcase_67	AC	2 ms 6,820 KB
testcase_68	AC	2 ms 6,820 KB
testcase_69	AC	2 ms 6,820 KB
testcase_70	AC	1 ms 6,820 KB
testcase_71	AC	2 ms 6,816 KB
testcase_72	AC	2 ms 6,816 KB
testcase_73	AC	52 ms 8,320 KB
testcase_74	AC	52 ms 8,320 KB
testcase_75	AC	30 ms 6,816 KB
testcase_76	AC	117 ms 13,312 KB
testcase_77	AC	85 ms 10,368 KB
testcase_78	AC	139 ms 14,720 KB
testcase_79	AC	6 ms 6,820 KB
testcase_80	AC	8 ms 6,816 KB
testcase_81	AC	167 ms 16,128 KB
testcase_82	AC	177 ms 16,384 KB
testcase_83	AC	173 ms 16,512 KB
testcase_84	AC	174 ms 16,384 KB
testcase_85	AC	173 ms 16,384 KB
testcase_86	AC	186 ms 16,384 KB
testcase_87	AC	178 ms 16,512 KB
testcase_88	AC	173 ms 16,384 KB
testcase_89	AC	186 ms 16,512 KB
testcase_90	AC	181 ms 16,384 KB
testcase_91	AC	182 ms 16,384 KB
testcase_92	AC	180 ms 16,384 KB
testcase_93	AC	2 ms 6,816 KB
testcase_94	AC	105 ms 16,384 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード