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

• 問題: No.855 ヘビの日光浴
• ユーザー: 梧桐
• 提出日時: 2026-05-19 14:24:11
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 121 ms / 3,153 ms
• コード長: 4,672 bytes
• コンパイル時間: 785 ms
• コンパイル使用メモリ: 100,636 KB
• 実行使用メモリ: 12,032 KB
• 最終ジャッジ日時: 2026-05-19 14:24:20
• 合計ジャッジ時間: 8,701 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 92

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:120:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  120 |     for (auto &[x, y, l] : ops) {
      |                ^
main.cpp:132:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  132 |     for (auto [x, y, l] : ops) {
      |               ^

ソースコード

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 100010, INF_KEY = 2000000000;
const LL INF_EXT = 1LL << 60;

struct Node { LL mx; };

struct SegTree {
    Node seg[N << 2];
    int sz, keys[N];
    void Init(const vector<int> &ks) {
        sz = ks.size();
        for (int i = 0; i < sz; ++i) {
            keys[i] = ks[i];
        }
    }
    void PushUp(int u) {
        seg[u].mx = max(seg[u << 1].mx, seg[u << 1 | 1].mx);
    }
    void Update(int u, int ul, int ur, int p, LL v) {
        if (ul == ur) { seg[u].mx = v; return; }
        int mid = ul + ur >> 1;
        if (p <= mid) Update(u << 1, ul, mid, p, v);
        else Update(u << 1 | 1, mid + 1, ur, p, v);
        PushUp(u);
    }
    void Update(int key, LL v) {
        auto it = lower_bound(keys, keys + sz, key);
        if (it == keys + sz || *it != key) return;
        Update(1, 1, sz, it - keys + 1, v);
    }
    LL Get(int u, int ul, int ur, int p) {
        if (ul == ur) return seg[u].mx;
        int mid = ul + ur >> 1;
        if (p <= mid) return Get(u << 1, ul, mid, p);
        return Get(u << 1 | 1, mid + 1, ur, p);
    }
    LL Get(int key) {
        auto it = lower_bound(keys, keys + sz, key);
        if (it == keys + sz || *it != key) return 0LL;
        return Get(1, 1, sz, it - keys + 1);
    }
    int QueryMin(int u, int ul, int ur, LL tgt) {
        if (seg[u].mx < tgt) return INF_KEY;
        if (ul == ur) return keys[ul - 1];
        int mid = ul + ur >> 1;
        if (seg[u << 1].mx >= tgt) return QueryMin(u << 1, ul, mid, tgt);
        return QueryMin(u << 1 | 1, mid + 1, ur, tgt);
    }
    int QueryMin(LL tgt) { return sz ? QueryMin(1, 1, sz, tgt) : INF_KEY; }
    int QueryMax(int u, int ul, int ur, LL tgt) {
        if (seg[u].mx < tgt) return -1;
        if (ul == ur) return keys[ul - 1];
        int mid = ul + ur >> 1;
        if (seg[u << 1 | 1].mx >= tgt) return QueryMax(u << 1 | 1, mid + 1, ur, tgt);
        return QueryMax(u << 1, ul, mid, tgt);
    }
    int QueryMax(LL tgt) { return sz ? QueryMax(1, 1, sz, tgt) : -1; }
    LL Sum(int u, int ul, int ur) {
        if (ul == ur) return seg[u].mx;
        int mid = ul + ur >> 1;
        return Sum(u << 1, ul, mid) + Sum(u << 1 | 1, mid + 1, ur);
    }
    LL Sum() { return sz ? Sum(1, 1, sz) : 0LL; }
};

struct Op { int x, y, l; };

SegTree sgt[4];
int w, h, n;
LL ans;

void ProcessMin(int s, int o, int c1, int c2, int key, int add, int dim, int th1, int th2) {
    LL new_val = sgt[s].Get(key) + add;
    LL cand1 = (dim + 1) - sgt[o].Get(key);
    int k2 = sgt[c1].QueryMin(th1), k3 = sgt[c2].QueryMin(th2);
    LL cand2 = k2 == INF_KEY ? INF_EXT : k2;
    LL cand3 = k3 == INF_KEY ? INF_EXT : k3;
    LL safe = min({ cand1, cand2, cand3 }) - 1;
    if (new_val <= safe) {
        sgt[s].Update(key, new_val);
    } else {
        sgt[s].Update(key, 0);
        if (cand1 == safe + 1) sgt[o].Update(key, 0);
        if (cand2 == safe + 1) sgt[c1].Update(k2, 0);
        if (cand3 == safe + 1) sgt[c2].Update(k3, 0);
    }
}

void ProcessMax(int s, int o, int c1, int c2, int key, int add, int dim, int th1, int th2) {
    LL new_val = sgt[s].Get(key) + add;
    LL cand1 = (dim + 1) - sgt[o].Get(key);
    int k2 = sgt[c1].QueryMax(th1), k3 = sgt[c2].QueryMax(th2);
    LL cand2 = k2 == -1 ? INF_EXT : (dim + 1) - k2;
    LL cand3 = k3 == -1 ? INF_EXT : (dim + 1) - k3;
    LL safe = min({ cand1, cand2, cand3 }) - 1;
    if (new_val <= safe) {
        sgt[s].Update(key, new_val);
    } else {
        sgt[s].Update(key, 0);
        if (cand1 == safe + 1) sgt[o].Update(key, 0);
        if (cand2 == safe + 1) sgt[c1].Update(k2, 0);
        if (cand3 == safe + 1) sgt[c2].Update(k3, 0);
    }
}

int main() {
    scanf("%d%d%d", &h, &w, &n);

    vector<Op> ops(n);
    set<int> sides[4];
    for (auto &[x, y, l] : ops) {
        scanf("%d%d%d", &x, &y, &l);
        if (x == 0) sides[0].insert(y);
        else if (x == w + 1) sides[1].insert(y);
        else if (y == 0) sides[2].insert(x);
        else sides[3].insert(x);
    }

    for (int i = 0; i < 4; ++i) {
        sgt[i].Init(vector<int>(sides[i].begin(), sides[i].end()));
    }

    for (auto [x, y, l] : ops) {
        if (x == 0) ProcessMin(0, 1, 2, 3, y, l, w, y, h + 1 - y);
        else if (x == w + 1) ProcessMax(1, 0, 2, 3, y, l, w, y, h + 1 - y);
        else if (y == 0) ProcessMin(2, 3, 0, 1, x, l, h, x, w + 1 - x);
        else ProcessMax(3, 2, 0, 1, x, l, h, x, w + 1 - x);
    }

    ans = 0LL;
    for (int i = 0; i < 4; ++i) {
        ans += sgt[i].Sum();
    }
    printf("%lld\n", ans);

    return 0;
}