結果

問題 No.855 ヘビの日光浴
コンテスト
ユーザー square1001
提出日時 2020-03-02 22:03:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,329 bytes
コンパイル時間 1,109 ms
コンパイル使用メモリ 91,124 KB
実行使用メモリ 168,852 KB
最終ジャッジ日時 2024-10-01 21:00:16
合計ジャッジ時間 47,544 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 91 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
class segmenttree {
private:
	int n, sz;
	unordered_map<int, int> val;
public:
	segmenttree() : n(0), sz(0) {};
	segmenttree(int n_) : n(n_) {
		sz = 1;
		while (sz < n) sz *= 2;
	}
	void update(int pos, int x) {
		pos += sz;
		val[pos] = x;
		while (pos > 1) {
			pos >>= 1;
			val[pos] = max(val[pos * 2], val[pos * 2 + 1]);
		}
	}
	int reachl(int x) {
		if (val[1] < x) return n + 2;
		int cur = 1;
		while (cur < sz) {
			cur *= 2;
			if (val[cur] < x) ++cur;
		}
		return cur - sz;
	}
	int reachr(int x) {
		if (val[1] < x) return -1 - 2;
		int cur = 1;
		while (cur < sz) {
			cur *= 2;
			if (val[cur + 1] >= x) ++cur;
		}
		return cur - sz;
	}
};
int sz[4];
unordered_map<int, int> dat[4];
segmenttree seg[4];
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];
	}
	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