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

提出ソース

結果

問題	No.855 ヘビの日光浴
ユーザー	noshi91
提出日時	2019-07-26 23:14:46
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,137 bytes
コンパイル時間	1,379 ms
コンパイル使用メモリ	98,548 KB
実行使用メモリ	11,648 KB
最終ジャッジ日時	2024-04-09 20:31:29
合計ジャッジ時間	6,695 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	1 ms 6,940 KB
testcase_13	AC	1 ms 6,940 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	2 ms 6,940 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	AC	2 ms 6,944 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	WA	-
testcase_30	AC	2 ms 6,944 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	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	AC	2 ms 6,940 KB
testcase_63	AC	1 ms 6,940 KB
testcase_64	WA	-
testcase_65	WA	-
testcase_66	AC	1 ms 6,940 KB
testcase_67	AC	1 ms 6,944 KB
testcase_68	AC	1 ms 6,940 KB
testcase_69	WA	-
testcase_70	AC	1 ms 6,940 KB
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	WA	-
testcase_84	WA	-
testcase_85	WA	-
testcase_86	WA	-
testcase_87	WA	-
testcase_88	WA	-
testcase_89	WA	-
testcase_90	WA	-
testcase_91	WA	-
testcase_92	WA	-
testcase_93	AC	2 ms 6,944 KB
testcase_94	AC	99 ms 11,392 KB

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

ソースコード

raw source code

//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>

namespace n91 {

using i8 = std::int_fast8_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u8 = std::uint_fast8_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr usize operator"" _z(unsigned long long x) noexcept {
  return static_cast<usize>(x);
}

class rep {
  const usize f, l;

public:
  class itr {
    friend rep;
    usize i;
    constexpr itr(const usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { ++i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr rep(const usize first, const usize last) noexcept
      : f(first), l(last) {}
  constexpr itr begin() const noexcept { return itr(f); }
  constexpr itr end() const noexcept { return itr(l); }
};
class revrep {
  const usize f, l;

public:
  class itr {
    friend revrep;
    usize i;
    constexpr itr(usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { --i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}
  constexpr itr begin() const noexcept { return itr(l); }
  constexpr itr end() const noexcept { return itr(f); }
};
template <class T> using vec_alias = std::vector<T>;
template <class T> auto md_vec(const usize n, const T &value) {
  return std::vector<T>(n, value);
}
template <class... Args> auto md_vec(const usize n, Args... args) {
  return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> constexpr T difference(const T &a, const T &b) {
  return a < b ? b - a : a - b;
}
template <class T> T scan() {
  T ret;
  std::cin >> ret;
  return ret;
}

} // namespace n91

#include <cassert>
#include <iterator>
#include <utility>
#include <vector>

template <class Monoid> class segment_tree {
public:
  using value_structure = Monoid;
  using value_type = typename value_structure::value_type;
  using container_type = std::vector<value_type>;
  using const_reference = typename container_type::const_reference;
  using size_type = typename container_type::size_type;

protected:
  static size_type getsize(const size_type size) {
    size_type ret = 1;
    while (ret < size)
      ret <<= 1;
    return ret;
  }

  size_type size_;
  container_type tree;

  size_type base_size() const { return tree.size() >> 1; }
  void recalc(const size_type index) {
    tree[index] =
        value_structure::operation(tree[index << 1], tree[index << 1 | 1]);
  }

public:
  segment_tree() : size_(0), tree() {}
  explicit segment_tree(const size_type size)
      : size_(size), tree(getsize(size) << 1, value_structure::identity()) {}
  template <class InputIterator>
  segment_tree(InputIterator first, InputIterator last)
      : size_(::std::distance(first, last)), tree() {
    const size_type cap = getsize(size_);
    tree.reserve(cap << 1);
    tree.resize(cap, value_structure::identity());
    tree.insert(tree.end(), first, last);
    tree.resize(cap << 1, value_structure::identity());
    for (size_type i = cap - 1; i; --i)
      recalc(i);
  }

  bool empty() const { return !size_; }
  size_type size() const { return size_; }

  const_reference operator[](const size_type index) const {
    assert(index < size());
    return tree[index + base_size()];
  }
  value_type fold(size_type first, size_type last) const {
    assert(first <= last);
    assert(first <= size());
    assert(last <= size());
    value_type ret_l = value_structure::identity(),
               ret_r = value_structure::identity();
    for (first += base_size(), last += base_size(); first < last;
         first >>= 1, last >>= 1) {
      if (first & 1)
        ret_l = value_structure::operation(::std::move(ret_l), tree[first++]);
      if (last & 1)
        ret_r = value_structure::operation(tree[last - 1], ::std::move(ret_r));
    }
    return value_structure::operation(::std::move(ret_l), ::std::move(ret_r));
  }
  template <class F> size_type search_left(const F &f) const {
    value_type acc = value_structure::identity();
    size_type i = 1;
    const size_type bs = base_size();
    while (i < bs) {
      if (!f(value_structure::operation(acc, tree[i <<= 1]))) {
        acc = value_structure::operation(std::move(acc), tree[i++]);
      }
    }
    return std::min(size() - 1, i - bs);
  }
  template <class F> size_type search_right(const F &f) const {
    value_type acc = value_structure::identity();
    size_type i = 1;
    const size_type bs = base_size();
    while (i < bs) {
      if (!f(value_structure::operation(tree[i = i * static_cast<size_type>(2) +
                                                 static_cast<size_type>(1)],
                                        acc))) {
        acc = value_structure::operation(tree[i--], std::move(acc));
      }
    }
    return std::min(size() - 1, i - bs);
  }

  template <class F> void update(size_type index, const F &f) {
    assert(index < size());
    index += base_size();
    tree[index] = f(::std::move(tree[index]));
    while (index >>= 1)
      recalc(index);
  }
};

#include <algorithm>
#include <limits>
template <class T> class max_monoid {
public:
  using value_type = T;
  static value_type operation(const value_type &x, const value_type &y) {
    return ::std::max(x, y);
  }
  static value_type identity() {
    return ::std::numeric_limits<value_type>::lowest();
  }
  static value_type reverse(const value_type &x) { return x; }
};

#include <algorithm>
#include <iostream>
#include <utility>

namespace n91 {

void main_() {
  const u64 h = scan<u64>();
  const u64 w = scan<u64>();
  const usize n = scan<usize>();
  struct query_type {
    u64 x, y, l;
  };
  std::vector<query_type> query(n);
  std::vector<u64> xs = {static_cast<u64>(0), w + static_cast<u64>(1)},
                   ys = {static_cast<u64>(0), h + static_cast<u64>(1)};
  for (auto &e : query) {
    std::cin >> e.x >> e.y >> e.l;
    xs.push_back(e.x);
    ys.push_back(e.y);
  }
  std::sort(xs.begin(), xs.end());
  xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
  const auto xi = [&xs](const u64 x) {
    return static_cast<usize>(std::distance(
        xs.cbegin(), std::lower_bound(xs.cbegin(), xs.cend(), x)));
  };
  const usize xn = xs.size();
  const auto xf = [&w](const u64 x) { return w + static_cast<u64>(1) - x; };
  std::sort(ys.begin(), ys.end());
  ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
  const auto yi = [&ys](const u64 y) {
    return static_cast<usize>(std::distance(
        ys.cbegin(), std::lower_bound(ys.cbegin(), ys.cend(), y)));
  };
  const usize yn = ys.size();
  const auto yf = [&h](const u64 y) { return h + static_cast<u64>(1) - y; };
  segment_tree<max_monoid<u64>> u(xn), d(xn), l(yn), r(yn);
  for (const auto &q : query) {
    if (q.y == static_cast<u64>(0)) {
      const u64 dlim = yf(d[xi(q.x)]);
      const u64 llim = ys[l.search_left([&](const u64 v) { return v >= q.x; })];
      const u64 rlim =
          ys[r.search_left([&](const u64 v) { return v >= xf(q.x); })];
      const u64 next = u[xi(q.x)] + q.l;
      if (next < llim && next < rlim && next < dlim) {
        u.update(xi(q.x), [&](auto) { return next; });
      } else if (dlim <= llim && dlim <= rlim) {
        u.update(xi(q.x), [&](auto) { return static_cast<u64>(0); });
        d.update(xi(q.x), [&](auto) { return static_cast<u64>(0); });
      } else if (llim < rlim) {
        u.update(xi(q.x), [&](auto) { return static_cast<u64>(0); });
        l.update(yi(llim), [&](auto) { return static_cast<u64>(0); });
      } else {
        u.update(xi(q.x), [&](auto) { return static_cast<u64>(0); });
        r.update(yi(rlim), [&](auto) { return static_cast<u64>(0); });
      }
    } else if (q.y == h + static_cast<u64>(1)) {
      const u64 ulim = yf(u[xi(q.x)]);
      const u64 llim =
          yf(ys[l.search_right([&](const u64 v) { return v >= q.x; })]);
      const u64 rlim =
          yf(ys[r.search_right([&](const u64 v) { return v >= xf(q.x); })]);
      const u64 next = d[xi(q.x)] + q.l;
      if (next < llim && next < rlim && next < ulim) {
        d.update(xi(q.x), [&](auto) { return next; });
      } else if (ulim <= llim && ulim <= rlim) {
        d.update(xi(q.x), [&](auto) { return static_cast<u64>(0); });
        u.update(xi(q.x), [&](auto) { return static_cast<u64>(0); });
      } else if (llim < rlim) {
        d.update(xi(q.x), [&](auto) { return static_cast<u64>(0); });
        l.update(yi(yf(llim)), [&](auto) { return static_cast<u64>(0); });
      } else {
        d.update(xi(q.x), [&](auto) { return static_cast<u64>(0); });
        r.update(yi(yf(rlim)), [&](auto) { return static_cast<u64>(0); });
      }
    } else if (q.x == static_cast<u64>(0)) {
      const u64 rlim = xf(r[yi(q.y)]);
      const u64 ulim = xs[u.search_left([&](const u64 v) { return v >= q.y; })];
      const u64 dlim =
          xs[d.search_left([&](const u64 v) { return v >= yf(q.y); })];
      const u64 next = l[yi(q.y)] + q.l;
      if (next < ulim && next < dlim && next < rlim) {
        l.update(yi(q.y), [&](auto) { return next; });
      } else if (rlim <= ulim && rlim <= dlim) {
        l.update(yi(q.y), [&](auto) { return static_cast<u64>(0); });
        r.update(yi(q.y), [&](auto) { return static_cast<u64>(0); });
      } else if (ulim < dlim) {
        l.update(yi(q.y), [&](auto) { return static_cast<u64>(0); });
        u.update(xi(ulim), [&](auto) { return static_cast<u64>(0); });
      } else {
        l.update(yi(q.y), [&](auto) { return static_cast<u64>(0); });
        d.update(xi(dlim), [&](auto) { return static_cast<u64>(0); });
      }
    } else {
      const u64 llim = xf(l[yi(q.y)]);
      const u64 ulim =
          xf(xs[u.search_right([&](const u64 v) { return v >= q.y; })]);
      const u64 dlim =
          xf(xs[r.search_right([&](const u64 v) { return v >= yf(q.y); })]);
      const u64 next = r[yi(q.y)] + q.l;
      if (next < ulim && next < dlim && next < llim) {
        r.update(yi(q.y), [&](auto) { return next; });
      } else if (llim <= ulim && llim <= dlim) {
        r.update(yi(q.y), [&](auto) { return static_cast<u64>(0); });
        l.update(yi(q.y), [&](auto) { return static_cast<u64>(0); });
      } else if (ulim < dlim) {
        r.update(yi(q.y), [&](auto) { return static_cast<u64>(0); });
        u.update(xi(xf(ulim)), [&](auto) { return static_cast<u64>(0); });
      } else {
        r.update(yi(q.y), [&](auto) { return static_cast<u64>(0); });
        d.update(xi(xf(dlim)), [&](auto) { return static_cast<u64>(0); });
      }
    }
  }
  u64 ans = static_cast<u64>(0);
  for (const auto i : rep(0_z, xn)) {
    ans += u[i];
    ans += d[i];
  }
  for (const auto i : rep(0_z, yn)) {
    ans += l[i];
    ans += r[i];
  }
  std::cout << ans << std::endl;
}

} // namespace n91

int main() {
  n91::main_();
  return 0;
}

yukicoder

結果

テストケース

ソースコード