結果
| 問題 | No.855 ヘビの日光浴 |
| コンテスト | |
| ユーザー |
 梧桐
|
| 提出日時 | 2026-05-19 04:00:34 |
| 言語 | C++14 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 176 ms / 3,153 ms |
| コード長 | 7,225 bytes |
| 記録 | |
| コンパイル時間 | 1,235 ms |
| コンパイル使用メモリ | 122,592 KB |
| 実行使用メモリ | 22,272 KB |
| 最終ジャッジ日時 | 2026-05-19 04:00:44 |
| 合計ジャッジ時間 | 9,202 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_1 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 92 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:212:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
212 | for (auto [x, y, l_add] : ops) {
| ^
main.cpp:220:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
220 | for (auto [k, v] : val_l) { ans += v; }
| ^
main.cpp:221:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
221 | for (auto [k, v] : val_r) { ans += v; }
| ^
main.cpp:222:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
222 | for (auto [k, v] : val_b) { ans += v; }
| ^
main.cpp:223:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
223 | for (auto [k, v] : val_t) { ans += v; }
| ^
ソースコード
#include <iostream>
#include <cstdio>
#include <set>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
const LL INF_EXT = 1LL << 60;
const int INF_KEY = 2000000000;
struct SegTree {
int n, sz;
vector<LL> tree;
vector<int> keys;
unordered_map<int, int> pos;
void Init(const vector<int> &sorted_keys) {
keys = sorted_keys;
sz = keys.size();
n = 1;
while (n < sz) { n *= 2; }
tree.assign(2 * n, 0);
pos.clear();
for (int i = 0; i < sz; ++i) {
pos[keys[i]] = i;
}
}
void Update(int key, LL value) {
if (pos.find(key) == pos.end()) return;
int idx = pos[key] + n;
tree[idx] = value;
for (idx /= 2; idx >= 1; idx /= 2) {
tree[idx] = max(tree[2 * idx], tree[2 * idx + 1]);
}
}
int QueryMin(LL threshold) {
if (tree[1] < threshold) return INF_KEY;
int idx = 1;
while (idx < n) {
int left = 2 * idx;
if (tree[left] >= threshold) idx = left;
else idx = left + 1;
}
return keys[idx - n];
}
int QueryMaxRec(int idx, int l, int r, LL threshold) {
if (r - l == 1) return tree[idx] >= threshold ? keys[l] : -1;
int mid = l + r >> 1;
int right = 2 * idx + 1, left = 2 * idx;
if (tree[right] >= threshold) return QueryMaxRec(right, mid, r, threshold);
if (tree[left] >= threshold) return QueryMaxRec(left, l, mid, threshold);
return -1;
}
int QueryMax(LL threshold) {
if (tree[1] < threshold) return -1;
return QueryMaxRec(1, 0, n, threshold);
}
};
SegTree seg_l, seg_r, seg_b, seg_t;
unordered_map<int, LL> val_l, val_r, val_b, val_t;
int w, h;
LL ans;
LL GetVal(char grp, int key) {
if (grp == 'L') return val_l.count(key) ? val_l[key] : 0LL;
if (grp == 'R') return val_r.count(key) ? val_r[key] : 0LL;
if (grp == 'B') return val_b.count(key) ? val_b[key] : 0LL;
return val_t.count(key) ? val_t[key] : 0LL;
}
void SetVal(char grp, int key, LL value) {
if (grp == 'L') {
val_l[key] = value;
seg_l.Update(key, value);
} else if (grp == 'R') {
val_r[key] = value;
seg_r.Update(key, value);
} else if (grp == 'B') {
val_b[key] = value;
seg_b.Update(key, value);
} else {
val_t[key] = value;
seg_t.Update(key, value);
}
}
void ProcessL(int y, LL add) {
LL cur = GetVal('L', y), new_val = cur + add;
LL r_val = GetVal('R', y);
LL cand1 = (w + 1) - r_val;
int cand2_key = seg_b.QueryMin(y);
LL cand2 = cand2_key == INF_KEY ? INF_EXT : cand2_key;
int cand3_key = seg_t.QueryMin((h + 1) - y);
LL cand3 = cand3_key == INF_KEY ? INF_EXT : cand3_key;
LL safe_max = min(min(cand1, cand2), cand3) - 1;
if (new_val <= safe_max) SetVal('L', y, new_val);
else {
SetVal('L', y, 0);
if (cand1 == safe_max + 1) SetVal('R', y, 0);
if (cand2 == safe_max + 1) SetVal('B', cand2_key, 0);
if (cand3 == safe_max + 1) SetVal('T', cand3_key, 0);
}
}
void ProcessR(int y, LL add) {
LL cur = GetVal('R', y), new_val = cur + add;
LL l_val = GetVal('L', y);
LL cand1 = (w + 1) - l_val;
int bottom_max = seg_b.QueryMax(y);
LL cand2 = bottom_max == -1 ? INF_EXT : (w + 1) - bottom_max;
int top_max = seg_t.QueryMax((h + 1) - y);
LL cand3 = top_max == -1 ? INF_EXT : (w + 1) - top_max;
LL safe_max = min(min(cand1, cand2), cand3) - 1;
if (new_val <= safe_max) SetVal('R', y, new_val);
else {
SetVal('R', y, 0);
if (cand1 == safe_max + 1) SetVal('L', y, 0);
if (cand2 == safe_max + 1) SetVal('B', bottom_max, 0);
if (cand3 == safe_max + 1) SetVal('T', top_max, 0);
}
}
void ProcessB(int x, LL add) {
LL cur = GetVal('B', x), new_val = cur + add;
LL t_val = GetVal('T', x);
LL cand1 = (h + 1) - t_val;
int cand2_key = seg_l.QueryMin(x);
LL cand2 = cand2_key == INF_KEY ? INF_EXT : cand2_key;
int cand3_key = seg_r.QueryMin((w + 1) - x);
LL cand3 = cand3_key == INF_KEY ? INF_EXT : cand3_key;
LL safe_max = min(min(cand1, cand2), cand3) - 1;
if (new_val <= safe_max) SetVal('B', x, new_val);
else {
SetVal('B', x, 0);
if (cand1 == safe_max + 1) SetVal('T', x, 0);
if (cand2 == safe_max + 1) SetVal('L', cand2_key, 0);
if (cand3 == safe_max + 1) SetVal('R', cand3_key, 0);
}
}
void ProcessT(int x, LL add) {
LL cur = GetVal('T', x), new_val = cur + add;
LL b_val = GetVal('B', x);
LL cand1 = (h + 1) - b_val;
int left_max = seg_l.QueryMax(x);
LL cand2 = left_max == -1 ? INF_EXT : (h + 1) - left_max;
int right_max = seg_r.QueryMax((w + 1) - x);
LL cand3 = right_max == -1 ? INF_EXT : (h + 1) - right_max;
LL safe_max = min(min(cand1, cand2), cand3) - 1;
if (new_val <= safe_max) SetVal('T', x, new_val);
else {
SetVal('T', x, 0);
if (cand1 == safe_max + 1) SetVal('B', x, 0);
if (cand2 == safe_max + 1) SetVal('L', left_max, 0);
if (cand3 == safe_max + 1) SetVal('R', right_max, 0);
}
}
/**
* 将边界蛇分四组 (Left/Right/Bottom/Top)，各组按 key 建线段树（维护最大延伸值）。
*
* 每次操作：new_val = cur + add
* safe_max = min(三方向阻挡距离) - 1
* 若 new_val ≤ safe_max → 更新延伸值；否则 → 撞到的蛇均缩回（置 0）
*
* 阻挡查询（以左蛇 (0,y) 为例）：
* - 对面右蛇 (W+1,y)：safe_max < (W+1) - r_val
* - 底部蛇 (x,0)：QueryMin(延伸值 ≥ y) 返回最小 x（即第一个挡住的列）
* - 顶部蛇 (x,H+1)：QueryMin(延伸值 ≥ H+1-y) 返回最小 x
*/
int main() {
int n;
scanf("%d%d%d", &h, &w, &n);
vector<tuple<int, int, LL>> ops;
ops.reserve(n);
set<int> s_l, s_r, s_b, s_t;
for (int i = 0, x, y; i < n; ++i) {
LL l_add;
scanf("%d%d%lld", &x, &y, &l_add);
ops.push_back({ x, y, l_add });
if (x == 0) s_l.insert(y);
else if (x == w + 1) s_r.insert(y);
else if (y == 0) s_b.insert(x);
else s_t.insert(x);
}
vector<int> vec_l(s_l.begin(), s_l.end());
vector<int> vec_r(s_r.begin(), s_r.end());
vector<int> vec_b(s_b.begin(), s_b.end());
vector<int> vec_t(s_t.begin(), s_t.end());
seg_l.Init(vec_l);
seg_r.Init(vec_r);
seg_b.Init(vec_b);
seg_t.Init(vec_t);
for (int y : vec_l) { val_l[y] = 0; seg_l.Update(y, 0); }
for (int y : vec_r) { val_r[y] = 0; seg_r.Update(y, 0); }
for (int x : vec_b) { val_b[x] = 0; seg_b.Update(x, 0); }
for (int x : vec_t) { val_t[x] = 0; seg_t.Update(x, 0); }
for (auto [x, y, l_add] : ops) {
if (x == 0) ProcessL(y, l_add);
else if (x == w + 1) ProcessR(y, l_add);
else if (y == 0) ProcessB(x, l_add);
else ProcessT(x, l_add);
}
ans = 0LL;
for (auto [k, v] : val_l) { ans += v; }
for (auto [k, v] : val_r) { ans += v; }
for (auto [k, v] : val_b) { ans += v; }
for (auto [k, v] : val_t) { ans += v; }
printf("%lld\n", ans);
return 0;
}