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

• 問題: No.855 ヘビの日光浴
• ユーザー: noshi91
• 提出日時: 2019-07-26 23:14:46
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 11,137 bytes
• コンパイル時間: 1,456 ms
• コンパイル使用メモリ: 95,472 KB
• 実行使用メモリ: 11,608 KB
• 最終ジャッジ日時: 2024-10-01 20:50:31
• 合計ジャッジ時間: 6,444 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 17 WA * 75

ソースコード

//#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;
}