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

提出ソース
結果

問題	No.1490 スライムと爆弾
ユーザー	hashiryo
提出日時	2022-08-17 02:51:17
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	14,655 bytes
コンパイル時間	2,616 ms
コンパイル使用メモリ	222,908 KB
実行使用メモリ	236,216 KB
最終ジャッジ日時	2024-10-03 22:28:26
合計ジャッジ時間	20,694 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	RE	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	AC	3 ms 5,248 KB
testcase_08	RE	-
testcase_09	RE	-
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	RE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	RE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	AC	2 ms 6,820 KB
testcase_24	AC	3 ms 6,816 KB
testcase_25	TLE	-
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 pos_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 F = std::nullptr_t>
  struct Node_B {
    using E = F;
    T val;
    pos_t range[K][2], pos[K];
    int ch[2] = {-1, -1};
  };
  template <bool sg_, bool du_, typename tEnable = void>
  struct Node_D : Node_B<M> {};
  template <bool sg_, bool du_>
  struct Node_D<sg_, du_, typename std::enable_if_t<sg_ && !du_>>
      : Node_B<typename M::T> {
    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, 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, 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;
  std::vector<Node> ns;

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

 private:
  inline void pushup(int i) {
    ns[i].sum = ns[i].val;
    if (ns[i].ch[0] != -1) ns[i].sum = M::op(ns[ns[i].ch[0]].sum, ns[i].sum);
    if (ns[i].ch[1] != -1) ns[i].sum = M::op(ns[i].sum, ns[ns[i].ch[1]].sum);
  }
  inline void propagate(int i, const E &x) {
    if (i == -1) return;
    ns[i].lazy_flg ? (M::composition(ns[i].lazy, x), x) : (ns[i].lazy = x);
    M::mapping(ns[i].val, x), ns[i].lazy_flg = true;
    if constexpr (monoid<M>::value) M::mapping(ns[i].sum, x);
  }
  inline void eval(int i) {
    if (!ns[i].lazy_flg) return;
    ns[i].lazy_flg = false;
    propagate(ns[i].ch[0], ns[i].lazy), propagate(ns[i].ch[1], ns[i].lazy);
  }
  inline void build(int &i, 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];
    });
    i = ns.size(), ns.push_back(Node{md->second});
    for (std::uint8_t j = K; j--; ns[i].pos[j] = md->first[j]) {
      auto [mn, mx] =
          std::minmax_element(bg, ed, [j](const PosVal &l, const PosVal &r) {
            return l.first[j] < r.first[j];
          });
      ns[i].range[j][0] = mn->first[j], ns[i].range[j][1] = mx->first[j];
    }
    if (std::uint8_t nex = (div + 1) % K; n > 1)
      build(ns[i].ch[0], bg, md, nex), build(ns[i].ch[1], md + 1, ed, nex);
    if constexpr (monoid<M>::value) pushup(i);
  }
  template <class F, class G, class H>
  inline T fold(int i, const F &in, const G &inall, const H &outall) {
    static_assert(monoid<M>::value, "\"fold\" is not available");
    if (i == -1 || outall(ns[i].range)) return M::ti();
    if (inall(ns[i].range)) return ns[i].sum;
    if constexpr (dual<M>::value) eval(i);
    T ret = M::op(fold(ns[i].ch[0], in, inall, outall),
                  fold(ns[i].ch[1], in, inall, outall));
    return in(ns[i].pos) ? M::op(ret, ns[i].val) : ret;
  }
  template <class F, class G, class H>
  inline void apply(int i, const F &in, const G &inall, const H &outall,
                    const E &x) {
    static_assert(dual<M>::value, "\"apply\" is not available");
    if (i == -1 || outall(ns[i].range)) return;
    if (inall(ns[i].range)) return propagate(i, x), void();
    if (eval(i); in(ns[i].pos)) M::mapping(ns[i].val, x);
    apply(ns[i].ch[0], in, inall, outall, x);
    apply(ns[i].ch[1], in, inall, outall, x);
    if constexpr (monoid<M>::value) pushup(i);
  }
  inline std::pair<T, bool> get(int i, const std::array<pos_t, K> &pos) {
    if (i == -1) return {M::ti(), false};
    bool myself = true;
    for (std::uint8_t j = K; j--; myself &= pos[j] == ns[i].pos[j])
      if (ns[i].range[j][1] < pos[j] || pos[j] < ns[i].range[j][0])
        return {M::ti(), false};
    if (myself) return {ns[i].val, true};
    if constexpr (dual<M>::value) eval(i);
    auto ret = get(ns[i].ch[0], pos);
    return !ret.second ? get(ns[i].ch[1], pos) : ret;
  }
  inline bool set(int i, const std::array<pos_t, K> &pos, const T &x) {
    if (i == -1) return false;
    bool myself = true;
    for (std::uint8_t j = K; j--; myself &= pos[j] == ns[i].pos[j])
      if (ns[i].range[j][1] < pos[j] || pos[j] < ns[i].range[j][0])
        return false;
    if constexpr (dual<M>::value) eval(i);
    bool ret = true;
    if (myself)
      ns[i].val = x;
    else if (!(ret = set(ns[i].ch[0], pos, x)))
      ret = set(ns[i].ch[1], pos, x);
    if constexpr (monoid<M>::value) pushup(i);
    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, pos_t>...>);
    Range r;
    std::uint8_t i = 0;
    for (auto &&x : {intervals...}) {
      std::vector<pos_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](pos_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](pos_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](pos_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) {
    int root;
    build(root, v.begin(), v.end());
  }
  T get(std::array<pos_t, K> pos) { return get(0, pos).first; }
  template <typename... Args>
  T get(Args... ids) {
    static_assert(sizeof...(ids) == K);
    static_assert(std::conjunction_v<std::is_convertible<Args, pos_t>...>);
    return get(0, {ids...}).first;
  }
  bool set(T x, std::array<pos_t, K> pos) { return set(0, pos, x); }
  template <typename... Args>
  bool set(T x, Args... ids) {
    static_assert(sizeof...(ids) == K);
    static_assert(std::conjunction_v<std::is_convertible<Args, pos_t>...>);
    return set(0, {ids...}, x);
  }
  T fold(const Range &r) {
    auto [in, inall, outall] = funcs(r);
    return fold(0, in, inall, outall);
  }
  template <typename... Args>
  T fold(std::initializer_list<Args> &&...intervals) {
    auto r = to_range(intervals...);
    auto [in, inall, outall] = funcs(r);
    return fold(0, in, inall, outall);
  }
  template <class F, class G, class H>
  T fold(const F &in, const G &inall, const H &outall) {
    return fold(0, in, inall, outall);
  }
  void apply(E x, const Range &r) {
    auto [in, inall, outall] = funcs(r);
    apply(0, in, inall, outall, x);
  }
  template <typename... Args>
  void apply(E x, std::initializer_list<Args> &&...intervals) {
    auto r = to_range(intervals...);
    auto [in, inall, outall] = funcs(r);
    apply(0, in, inall, outall, x);
  }
  template <class F, class G, class H>
  void apply(E x, const F &in, const G &inall, const H &outall) {
    apply(0, in, inall, outall, x);
  }
  void debug_output(int i) {
    if (i == -1) return;
    debugArray(ns[i].pos, K);
    debugMatrix(ns[i].range, K, 2);
    debug(ns[i].val);
    debug(ns[i].sum);
    debug_output(ns[i].ch[0]);
    debug_output(ns[i].ch[1]);
  }
  void debug_output() { debug_output(0); }
};

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

結果

テストケース

ソースコード
