結果

問題 No.869 ふたつの距離
コンテスト
ユーザー tiger2005
提出日時 2026-05-28 02:03:38
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 4,835 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,555 ms
コンパイル使用メモリ 343,772 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-28 02:04:18
合計ジャッジ時間 33,365 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 93
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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() {
  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 != h + 1)
      xs.push_back(qs[i].x);
    if (qs[i].y != 0 && qs[i].y != w + 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(w - 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 > h) {
        modifyR(yid, 0);
        continue;
      }

      modifyL(yid, newl);
    } else if (qs[i].x == h + 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(w - y + 1);
      if (pos1 != -1e9 && xs[pos1 - 1] < h - newl + 1)
        pos1 = -1e9;
      if (pos2 != -1e9 && xs[pos2 - 1] < h - newl + 1)
        pos2 = -1e9;

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

      if (Ln[yid] + newl > h) {
        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(h - 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 > w) {
        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(h - x + 1);
      if (pos1 != -1e9 && ys[pos1 - 1] < w - newl + 1)
        pos1 = -1e9;
      if (pos2 != -1e9 && ys[pos2 - 1] < w - newl + 1)
        pos2 = -1e9;

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

      if (Dn[xid] + newl > w) {
        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;
}
0