結果

問題 No.855 ヘビの日光浴
コンテスト
ユーザー square1001
提出日時 2020-03-02 22:24:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 375 ms / 3,153 ms
コード長 3,390 bytes
コンパイル時間 1,142 ms
コンパイル使用メモリ 98,664 KB
実行使用メモリ 35,740 KB
最終ジャッジ日時 2024-10-01 20:56:13
合計ジャッジ時間 9,466 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
class node {
public:
	int val, l, r;
	node() : val(0), l(-1), r(-1) {};
	node(int val_, int l_, int r_) : val(val_), l(l_), r(r_) {};
};
class segmenttree {
private:
	int n, sz;
	vector<node> val;
public:
	segmenttree() : n(0), sz(0) {};
	segmenttree(int n_) : n(n_) {
		sz = 1;
		while (sz < n) sz *= 2;
		val.push_back(node());
	}
	void update(int pos, int x) {
		vector<int> seq = { pos + sz };
		while (seq.back() > 1) {
			seq.push_back(seq.back() >> 1);
		}
		vector<int> ptr = { 0 };
		for (int i = int(seq.size()) - 2; i >= 0; --i) {
			if (seq[i] == seq[i + 1] * 2) {
				if (val[ptr.back()].l == -1) {
					val[ptr.back()].l = val.size();
					val.push_back(node());
				}
				ptr.push_back(val[ptr.back()].l);
			}
			else {
				if (val[ptr.back()].r == -1) {
					val[ptr.back()].r = val.size();
					val.push_back(node());
				}
				ptr.push_back(val[ptr.back()].r);
			}
		}
		val[ptr.back()].val = x;
		for (int i = int(ptr.size()) - 2; i >= 0; --i) {
			val[ptr[i]].val = max(val[ptr[i]].l != -1 ? val[val[ptr[i]].l].val : 0, val[ptr[i]].r != -1 ? val[val[ptr[i]].r].val : 0);
		}
	}
	int reachl(int x) {
		if (val[0].val < x) return n + 2;
		int ptr = 0, cur = 1;
		while (cur < sz) {
			if (val[ptr].l != -1 && val[val[ptr].l].val >= x) {
				ptr = val[ptr].l;
				cur = cur * 2;
			}
			else {
				ptr = val[ptr].r;
				cur = cur * 2 + 1;
			}
		}
		return cur - sz;
	}
	long long reachr(int x) {
		if (val[0].val < x) return -1 - 2;
		int ptr = 0, cur = 1;
		while (cur < sz) {
			if (val[ptr].r != -1 && val[val[ptr].r].val >= x) {
				ptr = val[ptr].r;
				cur = cur * 2 + 1;
			}
			else {
				ptr = val[ptr].l;
				cur = cur * 2;
			}
		}
		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;
}
0