#1166986 (C++23) No.855 ヘビの日光浴

• 問題: No.855 ヘビの日光浴
• ユーザー: tiger2005
• 提出日時: 2026-05-28 02:36:39
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 66 ms / 3,153 ms
• コード長: 4,913 bytes
• コンパイル時間: 2,500 ms
• コンパイル使用メモリ: 343,624 KB
• 実行使用メモリ: 11,180 KB
• 最終ジャッジ日時: 2026-05-28 02:36:50
• 合計ジャッジ時間: 6,252 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

int H, W, n;
using i64 = long long;

struct SegTree {
  i64 mx[400010];
  void modify(int x, int l, int r, int p, i64 k) {
    if (l == r) {
      mx[x] = k;
      return;
    }
    int m = (l + r) >> 1;
    if (p <= m)
      modify(x << 1, l, m, p, k);
    else
      modify(x << 1 | 1, m + 1, r, p, k);
    mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
  }

  int first(int x, int l, int r, i64 c) {
    if (l == r)
      return l;
    int m = (l + r) >> 1;
    if (mx[x << 1] >= c)
      return first(x << 1, l, m, c);
    return first(x << 1 | 1, m + 1, r, c);
  }

  int last(int x, int l, int r, i64 c) {
    if (l == r)
      return l;
    int m = (l + r) >> 1;
    if (mx[x << 1 | 1] >= c)
      return last(x << 1 | 1, m + 1, r, c);
    return last(x << 1, l, m, c);
  }

  int first(i64 c) {
    if (mx[1] < c)
      return 1e9;
    return first(1, 1, n, c);
  }

  int last(i64 c) {
    if (mx[1] < c)
      return -1e9;
    return last(1, 1, n, c);
  }
} L, R, D, U;

struct Query {
  int x, y, l;
} qs[100010];

vector<int> xs, ys;

i64 Ln[100010], Rn[100010], Dn[100010], Un[100010];

void modifyL(int pos, i64 val) {
  Ln[pos] = val;
  L.modify(1, 1, n, pos, val);
}

void modifyR(int pos, i64 val) {
  Rn[pos] = val;
  R.modify(1, 1, n, pos, val);
}

void modifyD(int pos, i64 val) {
  Dn[pos] = val;
  D.modify(1, 1, n, pos, val);
}

void modifyU(int pos, i64 val) {
  Un[pos] = val;
  U.modify(1, 1, n, pos, val);
}

int main() {
  // freopen("snake.in", "r", stdin);
  // freopen("snake.out", "w", stdout);
  scanf("%d%d%d", &H, &W, &n);
  for (int i = 1; i <= n; i ++) {
    scanf("%d%d%d", &qs[i].x, &qs[i].y, &qs[i].l);
    if (qs[i].x != 0 && qs[i].x != W + 1)
      xs.push_back(qs[i].x);
    if (qs[i].y != 0 && qs[i].y != H + 1)
      ys.push_back(qs[i].y);
  }

  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  sort(ys.begin(), ys.end());
  ys.erase(unique(ys.begin(), ys.end()), ys.end());
  
  for (int i = 1; i <= n; i ++) {
    if (qs[i].x == 0) {
      // L
      int y = qs[i].y;
      int yid = lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1;
      i64 newl = Ln[yid] + qs[i].l;
      modifyL(yid, 0);

      int pos1 = D.first(y), pos2 = U.first(H - y + 1);
      if (pos1 != 1e9 && xs[pos1 - 1] > newl)
        pos1 = 1e9;
      if (pos2 != 1e9 && xs[pos2 - 1] > newl)
        pos2 = 1e9;

      if (pos1 != 1e9 || pos2 != 1e9) {
        if (pos1 < pos2) {
          modifyD(pos1, 0);
        } else {
          modifyU(pos2, 0);
        }
        continue;
      }

      if (Rn[yid] + newl > W) {
        modifyR(yid, 0);
        continue;
      }

      modifyL(yid, newl);
    } else if (qs[i].x == W + 1) {
      // R
      int y = qs[i].y;
      int yid = lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1;
      i64 newl = Rn[yid] + qs[i].l;
      modifyR(yid, 0);

      int pos1 = D.last(y), pos2 = U.last(H - y + 1);
      if (pos1 != -1e9 && xs[pos1 - 1] < W - newl + 1)
        pos1 = -1e9;
      if (pos2 != -1e9 && xs[pos2 - 1] < W - newl + 1)
        pos2 = -1e9;

      if (pos1 != -1e9 || pos2 != -1e9) {
        if (pos1 > pos2) {
          modifyD(pos1, 0);
        } else {
          modifyU(pos2, 0);
        }
        continue;
      }

      if (Ln[yid] + newl > W) {
        modifyL(yid, 0);
        continue;
      }

      modifyR(yid, newl);
    } else if (qs[i].y == 0) {
      // D
      int x = qs[i].x;
      int xid = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
      i64 newl = Dn[xid] + qs[i].l;
      modifyD(xid, 0);

      int pos1 = L.first(x), pos2 = R.first(W - x + 1);
      if (pos1 != 1e9 && ys[pos1 - 1] > newl)
        pos1 = 1e9;
      if (pos2 != 1e9 && ys[pos2 - 1] > newl)
        pos2 = 1e9;

      if (pos1 != 1e9 || pos2 != 1e9) {
        if (pos1 < pos2) {
          modifyL(pos1, 0);
        } else {
          modifyR(pos2, 0);
        }
        continue;
      }

      if (Un[xid] + newl > H) {
        modifyU(xid, 0);
        continue;
      }

      modifyD(xid, newl);
    } else {
      // U
      int x = qs[i].x;
      int xid = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
      i64 newl = Un[xid] + qs[i].l;
      modifyU(xid, 0);

      int pos1 = L.last(x), pos2 = R.last(W - x + 1);
      if (pos1 != -1e9 && ys[pos1 - 1] < H - newl + 1)
        pos1 = -1e9;
      if (pos2 != -1e9 && ys[pos2 - 1] < H - newl + 1)
        pos2 = -1e9;

      if (pos1 != -1e9 || pos2 != -1e9) {
        if (pos1 > pos2) {
          modifyL(pos1, 0);
        } else {
          modifyR(pos2, 0);
        }
        continue;
      }

      if (Dn[xid] + newl > H) {
        modifyD(xid, 0);
        continue;
      }

      modifyU(xid, newl);
    }
  }

  i64 ans = 0;

  for (int i = 1; i <= n; i ++) {
    ans += Ln[i];
    ans += Rn[i];
    ans += Dn[i];
    ans += Un[i];
  }

  printf("%lld", ans);
  return 0;
}