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

提出ソース

結果

問題	No.855 ヘビの日光浴
ユーザー	square1001
提出日時	2020-03-02 21:58:19
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3,036 ms / 3,153 ms
コード長	2,399 bytes
コンパイル時間	1,526 ms
コンパイル使用メモリ	100,852 KB
実行使用メモリ	168,856 KB
最終ジャッジ日時	2024-10-01 20:56:00
合計ジャッジ時間	46,327 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 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,816 KB
testcase_06	AC	2 ms 6,824 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,820 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	2 ms 6,816 KB
testcase_17	AC	2 ms 6,820 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	2 ms 6,824 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	2 ms 6,820 KB
testcase_24	AC	2 ms 6,820 KB
testcase_25	AC	2 ms 6,816 KB
testcase_26	AC	2 ms 6,816 KB
testcase_27	AC	2 ms 6,816 KB
testcase_28	AC	2 ms 6,820 KB
testcase_29	AC	2 ms 6,820 KB
testcase_30	AC	2 ms 6,816 KB
testcase_31	AC	2 ms 6,816 KB
testcase_32	AC	2 ms 6,816 KB
testcase_33	AC	4 ms 6,820 KB
testcase_34	AC	3 ms 6,820 KB
testcase_35	AC	3 ms 6,820 KB
testcase_36	AC	3 ms 6,820 KB
testcase_37	AC	3 ms 6,820 KB
testcase_38	AC	4 ms 6,820 KB
testcase_39	AC	3 ms 6,820 KB
testcase_40	AC	4 ms 6,820 KB
testcase_41	AC	3 ms 6,820 KB
testcase_42	AC	3 ms 6,824 KB
testcase_43	AC	2 ms 6,820 KB
testcase_44	AC	3 ms 6,820 KB
testcase_45	AC	3 ms 6,820 KB
testcase_46	AC	3 ms 6,816 KB
testcase_47	AC	3 ms 6,816 KB
testcase_48	AC	3 ms 6,824 KB
testcase_49	AC	3 ms 6,816 KB
testcase_50	AC	3 ms 6,820 KB
testcase_51	AC	3 ms 6,820 KB
testcase_52	AC	2 ms 6,820 KB
testcase_53	AC	2 ms 6,820 KB
testcase_54	AC	2 ms 6,816 KB
testcase_55	AC	2 ms 6,820 KB
testcase_56	AC	2 ms 6,816 KB
testcase_57	AC	2 ms 6,820 KB
testcase_58	AC	2 ms 6,820 KB
testcase_59	AC	2 ms 6,820 KB
testcase_60	AC	2 ms 6,820 KB
testcase_61	AC	2 ms 6,820 KB
testcase_62	AC	2 ms 6,820 KB
testcase_63	AC	2 ms 6,824 KB
testcase_64	AC	3 ms 6,820 KB
testcase_65	AC	3 ms 6,820 KB
testcase_66	AC	2 ms 6,820 KB
testcase_67	AC	2 ms 6,816 KB
testcase_68	AC	3 ms 6,820 KB
testcase_69	AC	2 ms 6,820 KB
testcase_70	AC	2 ms 6,816 KB
testcase_71	AC	3 ms 6,820 KB
testcase_72	AC	2 ms 6,816 KB
testcase_73	AC	750 ms 56,272 KB
testcase_74	AC	882 ms 67,780 KB
testcase_75	AC	519 ms 44,444 KB
testcase_76	AC	1,658 ms 98,628 KB
testcase_77	AC	1,378 ms 90,760 KB
testcase_78	AC	2,493 ms 147,832 KB
testcase_79	AC	59 ms 12,436 KB
testcase_80	AC	94 ms 13,824 KB
testcase_81	AC	2,990 ms 168,316 KB
testcase_82	AC	3,036 ms 168,856 KB
testcase_83	AC	2,890 ms 154,680 KB
testcase_84	AC	2,825 ms 154,664 KB
testcase_85	AC	2,829 ms 154,892 KB
testcase_86	AC	2,853 ms 154,920 KB
testcase_87	AC	3,007 ms 154,948 KB
testcase_88	AC	2,779 ms 154,760 KB
testcase_89	AC	2,832 ms 154,792 KB
testcase_90	AC	2,909 ms 154,896 KB
testcase_91	AC	2,910 ms 154,624 KB
testcase_92	AC	2,838 ms 154,800 KB
testcase_93	AC	2 ms 6,820 KB
testcase_94	AC	235 ms 22,604 KB

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

ソースコード

raw source code

#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
class segmenttree {
private:
	long long n, sz;
	unordered_map<long long, int> val;
public:
	segmenttree() : n(0), sz(0) {};
	segmenttree(int n_) : n(n_) {
		sz = 1;
		while (sz < n) sz *= 2;
	}
	void update(long long pos, int x) {
		pos += sz;
		val[pos] = x;
		while (pos > 1) {
			pos >>= 1;
			val[pos] = max(val[pos * 2], val[pos * 2 + 1]);
		}
	}
	long long reachl(int x) {
		if (val[1] < x) return n + 2;
		long long cur = 1;
		while (cur < sz) {
			cur *= 2;
			if (val[cur] < x) ++cur;
		}
		return cur - sz;
	}
	long long reachr(int x) {
		if (val[1] < x) return -1 - 2;
		long long cur = 1;
		while (cur < sz) {
			cur *= 2;
			if (val[cur + 1] >= x) ++cur;
		}
		return cur - sz;
	}
};
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int H, W, Q;
	cin >> H >> W >> Q;
	vector<int> X(Q), Y(Q), L(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> Y[i] >> X[i] >> L[i]; --X[i], --Y[i];
	}
	vector<int> sz(4);
	vector<unordered_map<int, int> > dat(4);
	vector<segmenttree> seg(4);
	for (int i = 0; i < 4; ++i) {
		sz[i] = (i % 2 == 0 ? H : W);
		seg[i] = segmenttree(sz[i]);
	}
	for (int i = 0; i < Q; ++i) {
		int dir = -1, pos = -1;
		if (Y[i] == -1) {
			dir = 0, pos = X[i];
		}
		if (X[i] == H) {
			dir = 1, pos = Y[i];
		}
		if (Y[i] == W) {
			dir = 2, pos = H - X[i] - 1;
		}
		if (X[i] == -1) {
			dir = 3, pos = W - Y[i] - 1;
		}
		int val1 = seg[(dir + 1) % 4].reachl(sz[dir] - pos) + 1;
		int val2 = sz[(dir + 1) % 4] - dat[(dir + 2) % 4][sz[dir] - pos - 1] + 1;
		int val3 = sz[(dir + 1) % 4] - seg[(dir + 3) % 4].reachr(pos + 1);
		int mn = min({ val1, val2, val3 });
		int plen = dat[dir][pos] + L[i];
		if (plen < mn) {
			dat[dir][pos] = plen;
			seg[dir].update(pos, plen);
		}
		else {
			dat[dir][pos] = 0;
			seg[dir].update(pos, 0);
			if (mn == val2) {
				dat[(dir + 2) % 4][sz[dir] - pos - 1] = 0;
				seg[(dir + 2) % 4].update(sz[dir] - pos - 1, 0);
			}
			else if (mn == val1) {
				dat[(dir + 1) % 4][val1 - 1] = 0;
				seg[(dir + 1) % 4].update(val1 - 1, 0);
			}
			else {
				dat[(dir + 3) % 4][sz[(dir + 1) % 4] - val3] = 0;
				seg[(dir + 3) % 4].update(sz[(dir + 1) % 4] - val3, 0);
			}
		}
	}
	long long ans = 0;
	for (int i = 0; i < 4; ++i) {
		for (pair<int, int> j : dat[i]) {
			ans += j.second;
		}
	}
	cout << ans << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード