結果
| 問題 | No.1490 スライムと爆弾 |
| ユーザー |
 hashiryo
|
| 提出日時 | 2022-08-17 03:11:02 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,665 bytes |
| コンパイル時間 | 3,275 ms |
| コンパイル使用メモリ | 222,636 KB |
| 実行使用メモリ | 316,372 KB |
| 最終ジャッジ日時 | 2024-10-03 22:56:28 |
| 合計ジャッジ時間 | 32,462 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| 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
6,816 KB |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | AC | 2 ms
5,248 KB |
| testcase_11 | AC | 3 ms
5,248 KB |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | RE | - |
| testcase_21 | TLE | - |
| testcase_22 | RE | - |
| testcase_23 | AC | 2 ms
5,248 KB |
| testcase_24 | AC | 2 ms
5,248 KB |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
| testcase_30 | TLE | - |
ソースコード
#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;
int ch[2] = {-1, -1};
pos_t range[K][2], pos[K];
};
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, {-1, -1}});
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;
}