結果
| 問題 |
No.511 落ちゲー 〜手作業のぬくもり〜
|
| コンテスト | |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2019-04-03 16:04:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,526 bytes |
| コンパイル時間 | 1,212 ms |
| コンパイル使用メモリ | 98,928 KB |
| 最終ジャッジ日時 | 2025-01-07 01:22:22 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 29 WA * 3 |
ソースコード
#include <memory>
#include <iostream>
#include <vector>
#include <cassert>
#include <numeric>
#include <limits>
#include <algorithm>
// https://yukicoder.me/problems/no/511
template <typename T>
constexpr T popCount(const T u)
{
#ifdef __has_builtin
return u == 0 ? T(0) : (T)__builtin_popcountll(u);
#else
unsigned long long v = static_cast<unsigned long long>(u);
return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<T>(v * 0x0101010101010101ULL >> 56 & 0x7f);
#endif
}
template <typename T>
constexpr T log2p1(const T u)
{
#ifdef __has_builtin
return u == 0 ? T(0) : T(64 - __builtin_clzll(u));
#else
unsigned long long v = static_cast<unsigned long long>(u);
return v = static_cast<unsigned long long>(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), popCount(v);
#endif
}
template <typename T>
constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); }
template <typename T>
constexpr T msbp1(const T v) { return log2p1(v); }
template <typename T>
constexpr T lsbp1(const T v)
{
#ifdef __has_builtin
return __builtin_ffsll(v);
#else
return v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1);
#endif
}
template <typename T>
constexpr bool ispow2(const T v) { return popCount(v) == 1; }
template <typename T>
constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); }
template <typename T>
constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); }
//!=======================================================================!//
//! dP .d88888b !//
//! 88 88. "' !//
//! 88 .d8888b. d888888b dP dP 'Y88888b. .d8888b. .d8888b. !//
//! 88 88' '88 .d8P' 88 88 '8b 88ooood8 88' '88 !//
//! 88 88. .88 .Y8P 88. .88 d8' .8P 88. ... 88. .88 !//
//! 88888888P '88888P8 d888888P '8888P88 Y88888P '88888P' '8888P88 !//
//! .88 .88 !//
//! d8888P d8888P !//
//!=======================================================================!//
template <typename MAct>
class LazySeg
{
public:
using ValMonoid = typename MAct::ValMonoid;
using OpMonoid = typename MAct::OpMonoid;
using T = typename ValMonoid::T;
using F = typename OpMonoid::T;
LazySeg(const std::size_t N, const T initial = ValMonoid::id()) : size(N), depth(clog(size)), half(1 << depth), val(half << 1, ValMonoid::id()), op(half << 1, OpMonoid::id())
{
if (initial != ValMonoid::id()) {
std::fill(val.begin() + half, val.end(), initial);
for (std::size_t i = half - 1; i >= 1; i--) { up(i); }
}
}
template <typename InIt>
LazySeg(const InIt first, const InIt last) : size(std::distance(first, last)), depth(clog(size)), half(1 << depth), val(half << 1, ValMonoid::id()), op(half << 1, OpMonoid::id())
{
std::copy(first, last, val.begin() + half);
for (std::size_t i = half - 1; i >= 1; i--) { up(i); }
}
T get(const std::size_t a) { return assert(a < size), fold(a, a + 1); }
void set(std::size_t a, const T& v)
{
assert(a < size);
topDown(a += half), op[a] = OpMonoid::id(), val[a] = v;
while (a >>= 1) { up(a); }
}
T fold(std::size_t L, std::size_t R)
{
assert(L < R);
assert(R <= size);
topDown(L += half), topDown(R += half - 1);
T accl = ValMonoid::id(), accr = ValMonoid::id();
for (R++; L < R; L >>= 1, R >>= 1) {
if (L & 1) { accl = acc(accl, val[L++]); }
if (R & 1) { accr = acc(val[--R], accr); }
}
return acc(accl, accr);
}
void act(std::size_t L, std::size_t R, const F& f)
{
assert(L < R), assert(R <= size);
const std::size_t l = L + half, r = R + half;
topDown(L += half), topDown(R += half);
for (std::size_t ls = 1, rs = 1; L < R; L >>= 1, R >>= 1, ls <<= 1, rs <<= 1) {
if (L & 1) { update(L++, f, ls); }
if (R & 1) { update(--R, f, rs); }
}
bottomUp(l), bottomUp(r);
}
void debugPrint()
{
std::cerr << "[";
for (std::size_t i = 0; i < size; i++) { std::cerr << get(i) << (i + 1 == size ? "" : ","); }
std::cerr << "]\n";
}
private:
void up(const std::size_t i) { val[i] = acc(val[i << 1], val[i << 1 | 1]); }
void update(const std::size_t a, const F& f, const std::size_t l) { op[a] = compose(f, op[a]), val[a] = eval(f, val[a], l); }
void down(const std::size_t a, const std::size_t l) { update(a << 1, op[a], l >> 1), update(a << 1 | 1, op[a], l >> 1), op[a] = OpMonoid::id(); }
void topDown(const std::size_t a)
{
const std::size_t b = (a / (a & -a)) >> 1;
for (std::size_t i = 0, l = half; i < depth; i++, l >>= 1) {
const std::size_t v = a >> (depth - i);
if (v > b) { break; }
down(v, l);
}
}
void bottomUp(std::size_t a)
{
a = (a / (a & -a)) >> 1;
for (; a >= 1; a >>= 1) { up(a); }
}
const std::size_t size, depth, half;
std::vector<T> val;
std::vector<F> op;
const ValMonoid acc{};
const OpMonoid compose{};
const MAct eval{};
};
//!===============================================================================================!//
//! 888888ba 888888ba oo .d88888b dP !//
//! 88 '8b 88 '8b 88. "' 88 !//
//! a88aaaa8P' a88aaaa8P' dP 88d888b. 'Y88888b. .d8888b. .d8888b. 88d888b. .d8888b. 88d888b. !//
//! 88 88 '8b. 88 88' '88 '8b 88ooood8 88' '88 88' '88 88' '"" 88' '88 !//
//! 88 88 .88 88 88 88 d8' .8P 88. ... 88. .88 88 88. ... 88 88 !//
//! dP 88888888P dP dP dP Y88888P '88888P' '88888P8 dP '88888P' dP dP !//
//!===============================================================================================!//
template <typename Init, typename Advance, typename Check>
std::vector<std::size_t> PBinSearch(const std::size_t Q, const std::size_t N, const Init init, const Advance advance, const Check check)
{
struct R
{
std::size_t l, r; // [l,r]
std::vector<std::size_t> qs;
};
std::vector<R> Rs{{0, N, std::vector<std::size_t>(Q)}}, nRs;
std::iota(Rs.back().qs.begin(), Rs.back().qs.end(), 0);
std::vector<std::size_t> ans(Q, N + 1), former, latter;
nRs.reserve(Q), former.reserve(Q), latter.reserve(Q);
while (not Rs.empty()) {
init();
std::size_t t = 0;
for (const auto& range : Rs) {
const std::size_t l = range.l, r = range.r, m = (l + r) >> 1;
for (; t < m; t++) { advance(t); }
for (const std::size_t q : range.qs) {
if (l == r) {
ans[q] = l;
} else {
(check(q) ? former : latter).push_back(q);
}
}
if (not former.empty()) { nRs.push_back({l, m, former}); }
if (not latter.empty()) { nRs.push_back({m + 1, r, latter}); }
former.clear(), latter.clear();
}
std::swap(Rs, nRs), nRs.clear();
}
return ans;
}
//!============================!//
//! 8888ba.88ba oo !//
//! 88 '8b '8b !//
//! 88 88 88 dP 88d888b. !//
//! 88 88 88 88 88' '88 !//
//! 88 88 88 88 88 88 !//
//! dP dP dP dP dP dP !//
//!============================!//
template <typename X>
struct Min
{
using T = X;
T operator()(const T& a, const T& b) const { return std::min(a, b); }
static constexpr T id() { return std::numeric_limits<T>::max(); }
};
//!===================================!//
//! 888888ba dP !//
//! 88 '8b 88 !//
//! a88aaaa8P' 88 dP dP .d8888b. !//
//! 88 88 88 88 Y8ooooo. !//
//! 88 88 88. .88 88 !//
//! dP dP '88888P' '88888P' !//
//!===================================!//
template <typename X>
struct Plus
{
using T = X;
T operator()(const T& a, const T& b) const { return a + b; }
static constexpr T id() { return T{}; }
};
//!=====================================================================!//
//! 8888ba.88ba oo 888888ba dP !//
//! 88 '8b '8b 88 '8b 88 !//
//! 88 88 88 dP 88d888b. a88aaaa8P' 88 dP dP .d8888b. !//
//! 88 88 88 88 88' '88 88888888 88 88 88 88 Y8ooooo. !//
//! 88 88 88 88 88 88 88 88 88. .88 88 !//
//! dP dP dP dP dP dP dP dP '88888P' '88888P' !//
//!=====================================================================!//
template <typename VX, typename OX>
struct Min_Plus
{
using ValMonoid = Min<VX>;
using OpMonoid = Plus<OX>;
using VT = typename ValMonoid::T;
using OT = typename OpMonoid::T;
template <typename Ind>
VT operator()(const OT& f, const VT& x, const Ind) const { return x == ValMonoid::id() ? x : f + x; }
};
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::size_t N, W;
ll H;
std::cin >> N >> W >> H;
std::vector<int> a(N), x(N);
std::vector<ll> b(N);
for (std::size_t i = 0; i < N; i++) { std::cin >> a[i] >> b[i] >> x[i], x[i]--; }
using Seg = LazySeg<Min_Plus<ll, ll>>;
std::unique_ptr<Seg> segptr = std::make_unique<Seg>(W, 0LL);
auto init = [&]() { segptr = std::make_unique<Seg>(W, 0LL); };
auto advance = [&](const std::size_t t) { segptr->act(x[t], x[t] + a[t], b[t]); };
auto check = [&](const std::size_t i) { return segptr->get(i) >= H; };
const auto ans = PBinSearch(W, N, init, advance, check);
ll A = 0, B = 0;
for (std::size_t i = 0; i < W; i++) { (ans[i] % 2 == 1 ? A : B)++; }
std::cout << (A == B ? "DRAW" : A > B ? "A" : "B") << std::endl;
return 0;
}