#789137 (C++17) No.1490 スライムと爆弾

提出ソース
結果

問題	No.1490 スライムと爆弾
ユーザー	hashiryo
提出日時	2022-08-16 23:36:58
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	14,715 bytes
コンパイル時間	2,838 ms
コンパイル使用メモリ	218,876 KB
実行使用メモリ	254,184 KB
最終ジャッジ日時	2024-10-03 18:07:05
合計ジャッジ時間	8,330 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 10,496 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	5 ms 5,248 KB
testcase_03	AC	3 ms 5,248 KB
testcase_04	AC	4 ms 5,248 KB
testcase_05	AC	5 ms 5,248 KB
testcase_06	AC	3 ms 5,248 KB
testcase_07	AC	3 ms 5,248 KB
testcase_08	AC	4 ms 5,248 KB
testcase_09	AC	3 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	3 ms 5,248 KB
testcase_13	TLE	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>

#ifndef TEMP
#define TEMP
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &x) {
  return os << "(" << x.first << ", " << x.second << ")";
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {
  os << '[';
  for (int _ = 0, __ = vec.size(); _ < __; _++) os << (_ ? ", " : "") << vec[_];
  return os << ']';
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &s) {
  os << '{';
  int _ = 0;
  for (const auto &x : s) os << (_++ ? ", " : "") << x;
  return os << '}';
}
template <typename T, std::size_t _Nm>
std::ostream &operator<<(std::ostream &os, const std::array<T, _Nm> &arr) {
  os << '[' << arr[0];
  for (std::size_t _ = 1; _ < _Nm; _++) os << ", " << arr[_];
  return os << ']';
}
template <class Tup, std::size_t... I>
void print(std::ostream &os, const Tup &x, std::index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{(os << std::get<I>(x) << ", ", 0)...};
}
template <class... Args>
std::ostream &operator<<(std::ostream &os, const std::tuple<Args...> &x) {
  static constexpr std::size_t N = sizeof...(Args);
  os << "(";
  if constexpr (N >= 2) print(os, x, std::make_index_sequence<N - 1>());
  return os << std::get<N - 1>(x) << ")";
}
std::ostream &operator<<(std::ostream &os, std::int8_t x) {
  return os << (int)x;
}
std::ostream &operator<<(std::ostream &os, std::uint8_t x) {
  return os << (int)x;
}
std::ostream &operator<<(std::ostream &os, const __int128_t &v) {
  if (v == 0) os << "0";
  __int128_t tmp = v < 0 ? (os << "-", -v) : v;
  std::string s;
  while (tmp) s += '0' + (tmp % 10), tmp /= 10;
  return std::reverse(s.begin(), s.end()), os << s;
}
std::ostream &operator<<(std::ostream &os, const __uint128_t &v) {
  if (v == 0) os << "0";
  __uint128_t tmp = v;
  std::string s;
  while (tmp) s += '0' + (tmp % 10), tmp /= 10;
  return std::reverse(s.begin(), s.end()), os << s;
}
#ifdef __LOCAL
const std::string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m",
                  BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m",
                  NORMAL_CROSSED = "\033[0;9;37m", ITALIC = "\033[3m",
                  BOLD = "\033[1m", RED_BACKGROUND = "\033[1;41m",
                  NORMAL_FAINT = "\033[0;2m";
#define func_LINE_FILE                                                 \
  NORMAL_FAINT << " in " << BOLD << __func__ << NORMAL_FAINT << ITALIC \
               << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET
#define checkpoint() \
  std::cerr << BRIGHT_RED << "< check point! >" << func_LINE_FILE << '\n'
#define debug(x)                                                \
  std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) \
            << func_LINE_FILE << '\n'
#define debugArray(x, n)                                             \
  do {                                                               \
    std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = [" << x[0]; \
    for (int _ = 1; _ < (int)(n); ++_) std::cerr << ", " << x[_];    \
    std::cerr << "]" << func_LINE_FILE << '\n';                      \
  } while (0)
#define debugMatrix(x, h, w)                                       \
  do {                                                             \
    std::cerr << BRIGHT_CYAN << #x << "\n" << COLOR_RESET << "= "; \
    for (int _ = 0; (_) < (int)(h); ++_) {                         \
      std::cerr << ((_ ? "   [" : "[["));                          \
      for (int __ = 0; __ < (int)(w); ++__)                        \
        std::cerr << ((__ ? ", " : "")) << x[_][__];               \
      std::cerr << "]" << (_ + 1 == (int)(h) ? "]" : ",\n");       \
    }                                                              \
    std::cerr << func_LINE_FILE << '\n';                           \
  } while (0)
#else
#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif

template <class T>
auto compress(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  return
      [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };
}

struct ClosedSection {
  long long l, r;
  ClosedSection() : l(1), r(0) {}
  ClosedSection(long long l_, long long r_) : l(l_), r(r_) {}
  bool valid() { return l <= r; }
};
template <class Check>  // closed [l,r]
ClosedSection bin_search(const Check &isok, long long l, long long r) {
  bool res_l = isok(l), res_r = isok(r);
  if (res_l && res_r) return ClosedSection(l, r);
  if (!res_l && !res_r) return ClosedSection();
  long long lb = l, ub = r;
  for (long long x; ub - lb > 1;)
    (isok(x = (lb + ub) / 2) == res_l ? lb : ub) = x;
  return res_l ? ClosedSection(l, lb) : ClosedSection(ub, r);
}
template <class Check>
ClosedSection bin_search(const Check &isok, ClosedSection cs) {
  return cs.valid() ? bin_search(isok, cs.l, cs.r) : cs;
}
#endif

#ifndef HAS_CHECK
#define HAS_CHECK(member, Dummy)                              \
  template <class T>                                          \
  struct has_##member {                                       \
    template <class U, Dummy>                                 \
    static std::true_type check(U *);                         \
    static std::false_type check(...);                        \
    static T *mClass;                                         \
    static const bool value = decltype(check(mClass))::value; \
  };
#define HAS_MEMBER(member) HAS_CHECK(member, int dummy = (&U::member, 0))
#define HAS_TYPE(member) HAS_CHECK(member, class dummy = typename U::member)
#endif

template <std::uint8_t K, class id_t, class M>
class KDTree {
  HAS_MEMBER(op);
  HAS_MEMBER(ti);
  HAS_MEMBER(mapping);
  HAS_MEMBER(composition);
  HAS_TYPE(T);
  HAS_TYPE(E);
  template <class L>
  using monoid = std::conjunction<has_T<L>, has_op<L>, has_ti<L>>;
  template <class L>
  using dual =
      std::conjunction<has_T<L>, has_E<L>, has_mapping<L>, has_composition<L>>;
  template <class T, class tDerived, class F = std::nullptr_t>
  struct Node_B {
    using E = F;
    T val;
    id_t range[K][2], pos[K];
    tDerived *ch[2] = {nullptr, nullptr};
  };
  template <bool sg_, bool du_, typename tEnable = void>
  struct Node_D : Node_B<M, Node_D<sg_, du_, tEnable>> {};
  template <bool sg_, bool du_>
  struct Node_D<sg_, du_, typename std::enable_if_t<sg_ && !du_>>
      : Node_B<typename M::T, Node_D<sg_, du_>> {
    typename M::T sum;
  };
  template <bool sg_, bool du_>
  struct Node_D<sg_, du_, typename std::enable_if_t<!sg_ && du_>>
      : Node_B<typename M::T, Node_D<sg_, du_>, typename M::E> {
    typename M::E lazy;
    bool lazy_flg = false;
  };
  template <bool sg_, bool du_>
  struct Node_D<sg_, du_, typename std::enable_if_t<sg_ && du_>>
      : Node_B<typename M::T, Node_D<sg_, du_>, typename M::E> {
    typename M::T sum;
    typename M::E lazy;
    bool lazy_flg = false;
  };
  using Node = Node_D<monoid<M>::value, dual<M>::value>;
  using T = decltype(Node::val);
  using E = typename Node::E;
  Node *root;

 public:
  using PosVal = std::pair<std::array<id_t, K>, T>;
  using Iter = typename std::vector<PosVal>::iterator;
  using Range = std::array<std::array<id_t, 2>, K>;

 private:
  static inline void pushup(Node *t) {
    t->sum = t->val;
    if (t->ch[0]) t->sum = M::op(t->ch[0]->sum, t->sum);
    if (t->ch[1]) t->sum = M::op(t->sum, t->ch[1]->sum);
  }
  static inline void propagate(Node *t, const E &x) {
    if (!t) return;
    t->lazy_flg ? (M::composition(t->lazy, x), x) : (t->lazy = x);
    M::mapping(t->val, x), t->lazy_flg = true;
    if constexpr (monoid<M>::value) M::mapping(t->sum, x);
  }
  static inline void eval(Node *t) {
    if (!t->lazy_flg) return;
    t->lazy_flg = false;
    propagate(t->ch[0], t->lazy), propagate(t->ch[1], t->lazy);
  }
  static inline void build(Node *&t, Iter bg, Iter ed, std::uint8_t div = 0) {
    if (ed - bg < 1) return;
    const int n = ed - bg;
    auto md = bg + n / 2;
    std::nth_element(bg, md, ed, [div](const PosVal &l, const PosVal &r) {
      return l.first[div] < r.first[div];
    });
    if (!t) t = new Node{md->second};
    for (std::uint8_t i = K; i--; t->pos[i] = md->first[i]) {
      auto [mn, mx] =
          std::minmax_element(bg, ed, [i](const PosVal &l, const PosVal &r) {
            return l.first[i] < r.first[i];
          });
      t->range[i][0] = mn->first[i], t->range[i][1] = mx->first[i];
    }
    if (std::uint8_t nex = (div + 1) % K; n > 1)
      build(t->ch[0], bg, md, nex), build(t->ch[1], md + 1, ed, nex);
    if constexpr (monoid<M>::value) pushup(t);
  }
  template <class F, class G, class H>
  static inline T fold(Node *t, const F &in, const G &inall, const H &outall) {
    static_assert(monoid<M>::value, "\"fold\" is not available");
    if (!t || outall(t->range)) return M::ti();
    if (inall(t->range)) return t->sum;
    if constexpr (dual<M>::value) eval(t);
    T ret = M::op(fold(t->ch[0], in, inall, outall),
                  fold(t->ch[1], in, inall, outall));
    return in(t->pos) ? M::op(ret, t->val) : ret;
  }
  template <class F, class G, class H>
  static inline void apply(Node *t, const F &in, const G &inall,
                           const H &outall, const E &x) {
    static_assert(dual<M>::value, "\"apply\" is not available");
    if (!t || outall(t->range)) return;
    if (inall(t->range)) return propagate(t, x), void();
    if (eval(t); in(t->pos)) M::mapping(t->val, x);
    apply(t->ch[0], in, inall, outall, x);
    apply(t->ch[1], in, inall, outall, x);
    if constexpr (monoid<M>::value) pushup(t);
  }
  static inline std::pair<T, bool> get(Node *t,
                                       const std::array<id_t, K> &pos) {
    if (!t) return {M::ti(), false};
    bool myself = true;
    for (std::uint8_t i = K; i--; myself &= pos[i] == t->pos[i])
      if (t->range[i][1] < pos[i] || pos[i] < t->range[i][0])
        return {M::ti(), false};
    if (myself) return {t->val, true};
    if constexpr (dual<M>::value) eval(t);
    auto ret = get(t->ch[0], pos);
    return !ret.second ? get(t->ch[1], pos) : ret;
  }
  static inline bool set(Node *t, const std::array<id_t, K> &pos, const T &x) {
    if (!t) return false;
    bool myself = true;
    for (std::uint8_t i = K; i--; myself &= pos[i] == t->pos[i])
      if (t->range[i][1] < pos[i] || pos[i] < t->range[i][0]) return false;
    if constexpr (dual<M>::value) eval(t);
    bool ret = true;
    if (myself)
      t->val = x;
    else if (!(ret = set(t->ch[0], pos, x)))
      ret = set(t->ch[1], pos, x);
    if constexpr (monoid<M>::value) pushup(t);
    return ret;
  }
  template <typename... Args>
  static inline Range to_range(std::initializer_list<Args>... intervals) {
    static_assert(sizeof...(intervals) == K);
    static_assert(std::conjunction_v<std::is_same<Args, id_t>...>);
    Range r;
    std::uint8_t i = 0;
    for (auto &&x : {intervals...}) {
      std::vector<id_t> tmp(x);
      assert(tmp.size() == 2), assert(tmp[0] <= tmp[1]);
      r[i][0] = tmp[0], r[i][1] = tmp[1], i++;
    }
    return r;
  }
  static inline auto funcs(const Range &r) {
    return std::make_tuple(
        [r](id_t pos[K]) {
          for (std::uint8_t i = K; i--;)
            if (pos[i] < r[i][0] || r[i][1] < pos[i]) return false;
          return true;
        },
        [r](id_t range[K][2]) {
          for (std::uint8_t i = K; i--;)
            if (range[i][0] < r[i][0] || r[i][1] < range[i][1]) return false;
          return true;
        },
        [r](id_t range[K][2]) {
          for (std::uint8_t i = K; i--;)
            if (range[i][1] < r[i][0] || r[i][1] < range[i][0]) return true;
          return false;
        });
  }

 public:
  KDTree(std::vector<PosVal> v) : root(nullptr) {
    build(root, v.begin(), v.end());
  }
  T get(std::array<id_t, K> pos) const { return get(root, pos).first; }
  template <typename... Args>
  T get(Args... ids) const {
    static_assert(sizeof...(ids) == K);
    static_assert(std::conjunction_v<std::is_convertible<Args, id_t>...>);
    return get(root, {ids...}).first;
  }
  bool set(T x, std::array<id_t, K> pos) const { return set(root, pos, x); }
  template <typename... Args>
  bool set(T x, Args... ids) const {
    static_assert(sizeof...(ids) == K);
    static_assert(std::conjunction_v<std::is_convertible<Args, id_t>...>);
    return set(root, {ids...}, x);
  }
  T fold(const Range &r) const {
    auto [in, inall, outall] = funcs(r);
    return fold(root, in, inall, outall);
  }
  template <typename... Args>
  T fold(std::initializer_list<Args> &&...intervals) const {
    auto r = to_range(intervals...);
    auto [in, inall, outall] = funcs(r);
    return fold(root, in, inall, outall);
  }
  template <class F, class G, class H>
  T fold(const F &in, const G &inall, const H &outall) const {
    return fold(root, in, inall, outall);
  }
  void apply(E x, const Range &r) const {
    auto [in, inall, outall] = funcs(r);
    apply(root, in, inall, outall, x);
  }
  template <typename... Args>
  void apply(E x, std::initializer_list<Args> &&...intervals) const {
    auto r = to_range(intervals...);
    auto [in, inall, outall] = funcs(r);
    apply(root, in, inall, outall, x);
  }
  template <class F, class G, class H>
  void apply(E x, const F &in, const G &inall, const H &outall) const {
    apply(root, in, inall, outall, x);
  }
  void debug_output(Node *t) {
    if (!t) return;
    debugArray(t->pos, K);
    debugMatrix(t->range, K, 2);
    debug(t->val);
    debug(t->sum);
    debug_output(t->ch[0]);
    debug_output(t->ch[1]);
  }
  void debug_output() { debug_output(root); }
};

using namespace std;
struct RASQ {
  struct T {
    long long val;
    int sz;
  };
  using E = long long;
  static T ti() { return {0, 0}; }
  static T op(T l, T r) { return {l.val + r.val, l.sz + r.sz}; }
  static void mapping(T &v, E x) { v.val += x * v.sz; }
  static void composition(E &pre, E suf) { pre += suf; }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  using KDT = KDTree<2, int, RASQ>;
  int H, W, N, M;
  cin >> H >> W >> N >> M;
  vector<typename KDT::PosVal> v;
  for (int i = 1; i <= H; i++)
    for (int j = 1; j <= W; j++) v.push_back({{i, j}, {0, 1}});
  KDT kdt(v);
  int T[N], U[N], L[N], R[N], A[N];
  for (int i = 0; i < N; i++) cin >> T[i] >> U[i] >> L[i] >> R[i] >> A[i];
  while (M--) {
    int X, Y, B, C;
    cin >> X >> Y >> B >> C;
    kdt.apply(C, {X - B, X + B}, {Y - B, Y + B});
  }
  int ans = 0;
  for (int i = 0; i < N; i++)
    ans += kdt.fold({T[i], U[i]}, {L[i], R[i]}).val < A[i];
  cout << ans << '\n';
  return 0;
}
yukicoder

結果

テストケース

ソースコード
