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

提出ソース

結果

問題	No.855 ヘビの日光浴
ユーザー	pekempey
提出日時	2019-07-27 00:00:10
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,899 bytes
コンパイル時間	2,320 ms
コンパイル使用メモリ	191,400 KB
実行使用メモリ	8,960 KB
最終ジャッジ日時	2024-10-01 20:52:28
合計ジャッジ時間	9,643 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	WA	-
testcase_05	AC	2 ms 6,816 KB
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,816 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	WA	-
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	2 ms 6,820 KB
testcase_17	AC	2 ms 6,820 KB
testcase_18	WA	-
testcase_19	AC	2 ms 6,820 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	2 ms 6,816 KB
testcase_27	WA	-
testcase_28	AC	2 ms 6,820 KB
testcase_29	WA	-
testcase_30	AC	2 ms 6,820 KB
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	AC	1 ms 6,816 KB
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	AC	2 ms 6,816 KB
testcase_64	AC	2 ms 6,816 KB
testcase_65	WA	-
testcase_66	WA	-
testcase_67	AC	2 ms 6,820 KB
testcase_68	AC	2 ms 6,816 KB
testcase_69	WA	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-
testcase_81	WA	-
testcase_82	WA	-
testcase_83	AC	320 ms 8,820 KB
testcase_84	AC	325 ms 8,824 KB
testcase_85	AC	318 ms 8,820 KB
testcase_86	AC	311 ms 8,960 KB
testcase_87	AC	317 ms 8,816 KB
testcase_88	AC	329 ms 8,948 KB
testcase_89	AC	316 ms 8,760 KB
testcase_90	AC	320 ms 8,816 KB
testcase_91	AC	318 ms 8,948 KB
testcase_92	AC	322 ms 8,820 KB
testcase_93	AC	2 ms 6,820 KB
testcase_94	AC	185 ms 8,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

const int INF = 1.1e9;

struct MAX {
  int N;
  vector<int> dat;

  MAX(int n) {
    N = 1;
    while (N < n) N *= 2;
    dat.resize(N * 2, -INF);
  }

  void update(int k, int v) {
    k += N;
    dat[k] = v;
    while (k > 1) {
      k >>= 1;
      dat[k] = max(dat[k * 2], dat[k * 2 + 1]);
    }
  }

  int query(int l, int r) {
    l += N;
    r += N;
    int res = -INF;
    while (l <= r) {
      if ((l & 1) == 1) res = max(res, dat[l++]);
      if ((r & 1) == 0) res = max(res, dat[r--]);
      l >>= 1;
      r >>= 1;
    }
    return res;
  }
};

vector<int> uniq(vector<int> a) {
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end());
  return a;
}

int doko(const vector<int> &a, int x) {
  return lower_bound(a.begin(), a.end(), x) - a.begin();
}

int main() {
  int H, W, Q;
  cin >> H >> W >> Q;
  vector<int> X(Q), Y(Q), Z(Q);
  vector<int> DX{0, W + 1}, DY{0, H + 1};
  rep(i, Q) {
    cin >> X[i] >> Y[i] >> Z[i];
    DX.push_back(X[i]);
    DY.push_back(Y[i]);
  }
  DX = uniq(DX);
  DY = uniq(DY);
  MAX U(DX.size());
  MAX D(DX.size());
  MAX L(DY.size()); 
  MAX R(DY.size());
  vector<ll> nagasaU(DX.size(), 0);
  vector<ll> nagasaD(DX.size(), 0);
  vector<ll> nagasaL(DY.size(), 0);
  vector<ll> nagasaR(DY.size(), 0);
  // ha?
  rep(i, Q) {
    int x = doko(DX, X[i]);
    int y = doko(DY, Y[i]);
    tuple<int, int, int> ans(INF, INF, INF);
    if (X[i] == 0) { // hidari
      auto sawaruU = [&]() -> tuple<int, int, int> {
        int l = 0;
        int r = DX.size() - 1;
        while (r - l > 1) {
          int m = (l + r) / 2;
          (U.query(1, m) >= Y[i] ? r : l) = m;
        }
        return {DX[r], DX[r], 0};
      };
      auto sawaruD = [&]() -> tuple<int, int, int> {
        int l = 0;
        int r = DX.size() - 1;
        while (r - l > 1) {
          int m = (l + r) / 2;
          (H + 1 - D.query(1, m) <= Y[i] ? r : l) = m;
        }
        return {DX[r], DX[r], H + 1};
      };
      auto sawaruR = [&]() -> tuple<int, int, int> {
        return {W + 1 - nagasaR[y], W + 1, Y[i]};
      };
      ans = min({sawaruU(), sawaruD(), sawaruR()});
    } else if (X[i] == W + 1) { // migi
      auto sawaruU = [&]() -> tuple<int, int, int> {
        int l = 0;
        int r = DX.size() - 1;
        while (r - l > 1) {
          int m = (l + r) / 2;
          (U.query(m, DX.size() - 1) >= Y[i] ? l : r) = m;
        }
        return {W + 1 - DX[l], DX[l], 0};
      };
      auto sawaruD = [&]() -> tuple<int, int, int> {
        int l = 0;
        int r = DX.size() - 1;
        while (r - l > 1) {
          int m = (l + r) / 2;
          (H + 1 - D.query(m, DX.size() - 1) <= Y[i] ? l : r) = m;
        }
        return {W + 1 - DX[l], DX[l], H + 1};
      };
      auto sawaruL = [&]() -> tuple<int, int, int> {
        return {W + 1 - nagasaL[y], 0, Y[i]};
      };
      ans = min({sawaruU(), sawaruD(), sawaruL()});
    } else if (Y[i] == 0) { // ue
      auto sawaruL = [&]() -> tuple<int, int, int> {
        int l = 0;
        int r = DY.size() - 1;
        while (r - l > 1) {
          int m = (l + r) / 2;
          (L.query(1, m) >= X[i] ? r : l) = m;
        }
        return {DY[r], 0, DY[r]};
      };
      auto sawaruR = [&]() -> tuple<int, int, int> {
        int l = 0;
        int r = DY.size() - 1;
        while (r - l > 1) {
          int m = (l + r) / 2;
          (H + 1 - R.query(1, m) <= X[i] ? r : l) = m;
        }
        return {DY[r], W + 1, DY[r]};
      };
      auto sawaruD = [&]() -> tuple<int, int, int> {
        return {H + 1 - nagasaD[x], X[i], H + 1};
      };
      ans = min({sawaruL(), sawaruR(), sawaruD()});
    } else if (Y[i] == H + 1) { // sita
      auto sawaruL = [&]() -> tuple<int, int, int> {
        int l = 0;
        int r = DY.size();
        while (r - l > 1) {
          int m = (l + r) / 2;
          (L.query(m, DY.size() - 1) >= X[i] ? l : r) = m;
        }
        return {H + 1 - DY[l], 0, DY[l]};
      };
      auto sawaruR = [&]() -> tuple<int, int, int> {
        int l = 0;
        int r = DY.size();
        while (r - l > 1) {
          int m = (l + r) / 2;
          (W + 1 - R.query(m, DY.size() - 1) <= X[i] ? l : r) = m;
        }
        return {H + 1 - DY[l], W + 1, DY[l]};
      };
      auto sawaruU = [&]() -> tuple<int, int, int> {
        return {H + 1 - nagasaU[x], X[i], 0};
      };
      ans = min({sawaruL(), sawaruR(), sawaruU()});
    } else abort();
    auto modosu = [&](int x, int y) {
      int ix = doko(DX, x);
      int iy = doko(DY, y);
      if (y == 0) {
        nagasaU[ix] = 0;
        U.update(ix, 0);
      } else if (y == H + 1) {
        nagasaD[ix] = 0;
        D.update(ix, 0);
      } else if (x == 0) {
        nagasaL[iy] = 0;
        L.update(iy, 0);
      } else if (x == W + 1) {
        nagasaR[iy] = 0;
        R.update(iy, 0);
      } else abort();
    };
    auto nobasu = [&]() {
      if (Y[i] == 0) {
        nagasaU[x] += Z[i];
        if (nagasaU[x] >= get<0>(ans)) return false;
        U.update(x, nagasaU[x]);
      } else if (Y[i] == H + 1) {
        nagasaD[x] += Z[i];
        if (nagasaD[x] >= get<0>(ans)) return false;
        D.update(x, nagasaD[x]);
      } else if (X[i] == 0) {
        nagasaL[y] += Z[i];
        if (nagasaL[y] >= get<0>(ans)) return false;
        L.update(y, nagasaL[y]);
      } else if (X[i] == W + 1) {
        nagasaR[y] += Z[i];
        if (nagasaR[y] >= get<0>(ans)) return false;
        R.update(y, nagasaR[y]);
      }
      return true;
    };
    if (!nobasu()) {
      modosu(get<1>(ans), get<2>(ans));
      modosu(X[i], Y[i]);
    }
  }
  ll ans = 0;
  rep(i, DY.size()) ans += nagasaL[i] + nagasaR[i];
  rep(i, DX.size()) ans += nagasaU[i] + nagasaD[i];
  cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード