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

提出ソース

結果

問題	No.855 ヘビの日光浴
ユーザー	pekempey
提出日時	2019-07-27 01:43:56
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	341 ms / 3,153 ms
コード長	3,804 bytes
コンパイル時間	2,213 ms
コンパイル使用メモリ	191,560 KB
実行使用メモリ	14,692 KB
最終ジャッジ日時	2024-04-09 20:34:02
合計ジャッジ時間	9,155 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,812 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	1 ms 6,940 KB
testcase_14	AC	1 ms 6,940 KB
testcase_15	AC	1 ms 6,944 KB
testcase_16	AC	1 ms 6,944 KB
testcase_17	AC	1 ms 6,940 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	1 ms 6,940 KB
testcase_21	AC	1 ms 6,944 KB
testcase_22	AC	1 ms 6,940 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	1 ms 6,944 KB
testcase_26	AC	1 ms 6,944 KB
testcase_27	AC	1 ms 6,940 KB
testcase_28	AC	1 ms 6,940 KB
testcase_29	AC	1 ms 6,944 KB
testcase_30	AC	1 ms 6,940 KB
testcase_31	AC	1 ms 6,944 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	3 ms 6,940 KB
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	2 ms 6,944 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	2 ms 6,944 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	3 ms 6,944 KB
testcase_41	AC	2 ms 6,940 KB
testcase_42	AC	1 ms 6,944 KB
testcase_43	AC	1 ms 6,944 KB
testcase_44	AC	2 ms 6,940 KB
testcase_45	AC	2 ms 6,940 KB
testcase_46	AC	3 ms 6,940 KB
testcase_47	AC	2 ms 6,940 KB
testcase_48	AC	2 ms 6,940 KB
testcase_49	AC	3 ms 6,944 KB
testcase_50	AC	2 ms 6,940 KB
testcase_51	AC	2 ms 6,944 KB
testcase_52	AC	1 ms 6,940 KB
testcase_53	AC	1 ms 6,944 KB
testcase_54	AC	1 ms 6,944 KB
testcase_55	AC	1 ms 6,940 KB
testcase_56	AC	1 ms 6,940 KB
testcase_57	AC	2 ms 6,944 KB
testcase_58	AC	2 ms 6,944 KB
testcase_59	AC	2 ms 6,944 KB
testcase_60	AC	1 ms 6,944 KB
testcase_61	AC	1 ms 6,940 KB
testcase_62	AC	2 ms 6,940 KB
testcase_63	AC	1 ms 6,940 KB
testcase_64	AC	1 ms 6,940 KB
testcase_65	AC	2 ms 6,944 KB
testcase_66	AC	2 ms 6,944 KB
testcase_67	AC	1 ms 6,944 KB
testcase_68	AC	1 ms 6,940 KB
testcase_69	AC	1 ms 6,940 KB
testcase_70	AC	2 ms 6,944 KB
testcase_71	AC	1 ms 6,940 KB
testcase_72	AC	1 ms 6,940 KB
testcase_73	AC	97 ms 8,120 KB
testcase_74	AC	93 ms 7,824 KB
testcase_75	AC	51 ms 6,944 KB
testcase_76	AC	209 ms 12,676 KB
testcase_77	AC	150 ms 9,256 KB
testcase_78	AC	249 ms 13,396 KB
testcase_79	AC	10 ms 6,944 KB
testcase_80	AC	13 ms 6,944 KB
testcase_81	AC	275 ms 14,248 KB
testcase_82	AC	293 ms 14,464 KB
testcase_83	AC	323 ms 14,464 KB
testcase_84	AC	324 ms 14,592 KB
testcase_85	AC	323 ms 14,464 KB
testcase_86	AC	325 ms 14,464 KB
testcase_87	AC	335 ms 14,464 KB
testcase_88	AC	341 ms 14,588 KB
testcase_89	AC	332 ms 14,592 KB
testcase_90	AC	322 ms 14,468 KB
testcase_91	AC	322 ms 14,692 KB
testcase_92	AC	319 ms 14,588 KB
testcase_93	AC	2 ms 6,940 KB
testcase_94	AC	172 ms 14,592 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.01e9;

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

  Kitune(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();
}

template<class T1, class T2, class T3>
ostream &operator<<(ostream &o, tuple<T1, T2, T3> t) {
  return o << '(' << get<0>(t) << ',' << get<1>(t) << ','<< get<2>(t) << ')';
}

int main() {
  int H, W, Q;
  cin >> H >> W >> Q;
  vector<int> X(Q), Y(Q), Z(Q);
  vector<vector<int>> zisyo{{0, H + 1}, {0, W + 1}};
  rep(i, Q) {
    cin >> X[i] >> Y[i] >> Z[i];
    zisyo[0].push_back(Y[i]);
    zisyo[0].push_back(H + 1 - Y[i]);
    zisyo[1].push_back(X[i]);
    zisyo[1].push_back(W + 1 - X[i]);
  }
  zisyo[0] = uniq(zisyo[0]);
  zisyo[1] = uniq(zisyo[1]);
  zisyo.emplace_back();
  zisyo.emplace_back();
  for (int x : zisyo[0]) zisyo[2].push_back(H + 1 - x);
  for (int x : zisyo[1]) zisyo[3].push_back(W + 1 - x);
  reverse(zisyo[2].begin(), zisyo[2].end());
  reverse(zisyo[3].begin(), zisyo[3].end());
  vector<Kitune> ktn;
  vector<vector<ll>> nagasa;
  rep(i, 4) ktn.emplace_back(zisyo[i].size());
  rep(i, 4) nagasa.emplace_back(zisyo[i].size());
  rep(i, Q) {
    int k, z;
    if (X[i] == 0) { k = 0; z = Y[i]; }
    else if (Y[i] == 0) { k = 1; z = W + 1 - X[i]; }
    else if (X[i] == W + 1) { k = 2; z = H + 1 - Y[i]; } 
    else if (Y[i] == H + 1) { k = 3; z = X[i]; }
    else abort();
    auto hidarite = [&]() -> tuple<int, int, int> {
      int butukaru = 0;
      int butukaranai = zisyo[(k + 1) % 4].size() - 1;
      while (butukaranai - butukaru > 1) {
        int aida = (butukaru + butukaranai) / 2;
        if (ktn[(k + 1) % 4].query(aida, zisyo[(k + 1) % 4].size() - 1) >= z) {
          butukaru = aida;
        } else {
          butukaranai = aida;
        }
      }
      return {zisyo[(k + 1) % 4].back() - zisyo[(k + 1) % 4][butukaru], 1, butukaru};
    };
    auto migite = [&]() -> tuple<int, int, int> {
      int butukaru = zisyo[(k + 3) % 4].size() - 1;
      int butukaranai = 0;
      while (butukaru - butukaranai > 1) {
        int aida = (butukaru + butukaranai) / 2;
        if (ktn[(k + 3) % 4].query(0, aida) >= zisyo[k].back() - z) {
          butukaru = aida;
        } else {
          butukaranai = aida;
        }
      }
      return {zisyo[(k + 3) % 4][butukaru], 3, butukaru};
    };
    auto mukai = [&]() -> tuple<int, int, int> {
      int s = doko(zisyo[(k + 2) % 4], zisyo[k].back() - z);
      return {zisyo[(k + 1) % 4].back() - nagasa[(k + 2) % 4][s], 2, s};
    };
    auto hazime_ni_butukaru = min({hidarite(), migite(), mukai()});
    int zi = doko(zisyo[k % 2], z);
    auto kakikae = [&](int k, int z, int v) {
      k %= 4;
      nagasa[k][z] = v;
      ktn[k].update(z, v);
    };
    kakikae(k, zi, nagasa[k][zi] + Z[i]);
    if (nagasa[k][zi] >= get<0>(hazime_ni_butukaru)) {
      kakikae(k, zi, 0);
      kakikae(k + get<1>(hazime_ni_butukaru), get<2>(hazime_ni_butukaru), 0);
    }
  }
  ll ans = 0;
  rep(i, 4) for (int x : nagasa[i]) ans += x;
  cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード