結果
| 問題 |
No.511 落ちゲー 〜手作業のぬくもり〜
|
| コンテスト | |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2017-12-31 05:37:07 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,898 ms / 4,000 ms |
| コード長 | 9,446 bytes |
| コンパイル時間 | 3,206 ms |
| コンパイル使用メモリ | 221,012 KB |
| 最終ジャッジ日時 | 2025-01-05 06:47:36 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 32 |
ソースコード
#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ll = long long;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
os << "sz:" << v.size() << "\n[";
for (const auto& p : v) {
os << p << ",";
}
os << "]\n";
return os;
}
template <typename T>
vector<T> Vec(int n, T v)
{
return vector<T>(n, v);
}
template <class... Args>
auto Vec(int n, Args... args)
{
auto val = Vec(args...);
return vector<decltype(val)>(n, move(val));
}
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;
template <typename Base>
class SegmentTree
{
public:
using BaseAlgebra = Base;
using AccMonoid = typename BaseAlgebra::AccMonoid;
using OpMonoid = typename BaseAlgebra::OpMonoid;
using T = typename BaseAlgebra::T;
using F = typename BaseAlgebra::OpMonoid::T;
SegmentTree(const int n) : data_num(n), size(1 << (1 + __lg(2 * data_num - 1))), half(size >> 1), value(size, AccMonoid::identity()), action(size, OpMonoid::identity()) { assert(n > 0); }
SegmentTree(const std::vector<T>& val) : data_num(val.size()), size(1 << (1 + __lg(2 * data_num - 1))), half(size >> 1), value(size), action(size, OpMonoid::identity())
{
for (int data = 0; data < half; data++) {
if (data < data_num) {
value[data + half] = val[data];
} else {
value[data + half] = AccMonoid::identity();
}
}
for (int node = half - 1; node >= 1; node--) {
value[node] = acc(value[2 * node], value[2 * node + 1]);
}
}
void initialize()
{
for (int i = 0; i < size; i++) {
value[i] = AccMonoid::identity();
action[i] = OpMonoid::identity();
}
}
void initialize(const vector<T>& val)
{
for (int data = 0; data < half; data++) {
if (data < data_num) {
value[data + half] = val[data];
} else {
value[data + half] = AccMonoid::identity();
}
}
for (int node = half - 1; node >= 1; node--) {
value[node] = acc(value[2 * node], value[2 * node + 1]);
}
}
T get(const int a) const
{
assert(0 <= a and a < data_num);
return accumulate(a, a + 1);
}
void set(const int a, const T& val)
{
assert(0 <= a and a < data_num);
const int node = a + half;
value[node] = val;
for (int i = node / 2; i > 0; i /= 2) {
value[i] = acc(value[2 * i], value[2 * i + 1]);
}
}
T accumulate(const int a, const int b) const // Accumulate (a,b]
{
assert(0 <= a and a < b and b <= data_num);
return accumulateRec(1, 0, half, a, b);
}
void modify(const int a, const int b, const F& f) // Apply f on (a,b]
{
assert(0 <= a and a < b and b <= data_num);
if (f == OpMonoid::identity()) {
return;
}
modifyRec(1, 0, half, a, b, f);
}
int query(const int a, const int b) const // query (a,b]
{
assert(0 <= a and a < b and b <= data_num);
return queryRec(1, 0, half, a, b);
}
private:
void modifyRec(const int range_index, const int range_left, const int range_right, const int op_left, const int op_right, const F& f)
{
if (op_left <= range_left and range_right <= op_right) {
value[range_index] = act(f, value[range_index]);
action[range_index] = compose(f, action[range_index]);
} else if (range_right <= op_left or op_right <= range_left) {
// Do nothing
} else {
modifyRec(2 * range_index, range_left, (range_left + range_right) / 2, 0, half, action[range_index]);
modifyRec(2 * range_index, range_left, (range_left + range_right) / 2, op_left, op_right, f);
modifyRec(2 * range_index + 1, (range_left + range_right) / 2, range_right, 0, half, action[range_index]);
modifyRec(2 * range_index + 1, (range_left + range_right) / 2, range_right, op_left, op_right, f);
value[range_index] = acc(value[2 * range_index], value[2 * range_index + 1]);
action[range_index] = OpMonoid::identity();
}
}
T accumulateRec(const int range_index, const int range_left, const int range_right, const int op_left, const int op_right) const
{
if (op_left <= range_left and range_right <= op_right) {
return value[range_index];
} else if (range_right <= op_left or op_right <= range_left) {
return AccMonoid::identity();
} else {
return act(action[range_index], acc(accumulateRec(2 * range_index, range_left, (range_left + range_right) / 2, op_left, op_right),
accumulateRec(2 * range_index + 1, (range_left + range_right) / 2, range_right, op_left, op_right)));
}
}
int queryRec(const int range_index, const int range_left, const int range_right, const int op_left, const int op_right) const
{
if (op_left <= range_left and range_right <= op_right) {
return value[range_index];
} else if (range_right <= op_left or op_right <= range_left) {
return AccMonoid::identity();
} else {
return queryRec(2 * range_index, range_left, (range_left + range_right) / 2, op_left, op_right) + queryRec(2 * range_index + 1, (range_left + range_right) / 2, range_right, op_left, op_right);
}
}
const int data_num; // Num of valid data on leaves.
const int size;
const int half;
vector<T> value; // Tree for value(length: size)
vector<F> action; // Tree for action(length: half)
bool has_lazy;
const AccMonoid acc{};
const OpMonoid compose{};
const BaseAlgebra act{};
};
struct Sum_Plus {
using T = ll;
struct AccMonoid {
T operator()(const T& a, const T& b) const { return a + b; }
static constexpr T identity() { return 0; }
};
struct OpMonoid {
using T = ll;
T operator()(const T& f1, const T& f2) const { return f1 + f2; }
static constexpr T identity() { return 0; }
};
T operator()(const OpMonoid::T& f, const T& x) const { return f + x; }
};
template <typename Data, typename Checker>
void ParallelBinarySearch(const vector<Data>& queries, Checker& checker, const int inf, const int sup, vector<int>& ans)
{
const int Q = queries.size();
ans.resize(Q, INF<int>);
using Query = pair<Data, int>;
struct Qset {
int l;
int r;
vector<Query> query;
};
vector<Qset> data{Qset{inf, sup, vector<Query>(Q)}};
for (int i = 0; i < Q; i++) {
data[0].query[i] = make_pair(queries[i], i);
}
for (int d = 0;; d++) {
if (data.empty()) {
break;
}
vector<Qset> next;
checker.initialize();
int pos = 0;
for (const auto& dat : data) {
const int inf = dat.l;
const int sup = dat.r;
const int mid = (inf + sup) / 2;
Qset former{inf, mid, vector<Query>{}};
Qset latter{mid + 1, sup, vector<Query>{}};
for (; pos < mid; pos++) {
checker.update(pos);
}
if (inf >= sup - 1) {
for (const auto& e : dat.query) {
if (checker.check(e.first)) {
ans[e.second] = inf;
} else if (inf == sup - 1) {
latter.query.push_back(e);
}
}
} else {
for (const auto& e : dat.query) {
if (checker.check(e.first)) {
former.query.push_back(e);
} else {
latter.query.push_back(e);
}
}
}
if (not former.query.empty()) {
next.push_back(former);
}
if (not latter.query.empty()) {
next.push_back(latter);
}
}
data = next;
}
}
using Data = int;
struct Op {
ll a;
ll b;
ll x;
};
vector<Op> op;
int N;
ll H;
ll W;
// Checker::initialize() => void
// Checker::update(int pos) => void
// Checker::check(const Data&) => bool
struct Checker {
Checker() : seg(W) {}
void initialize()
{
seg.initialize();
}
void update(const int pos)
{
const auto& q = op[pos];
const ll l = q.x;
const ll r = q.a + q.x;
seg.modify(l, r, q.b);
}
bool check(const Data& data)
{
return seg.get(data) >= H;
}
SegmentTree<Sum_Plus> seg;
};
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
cin >> W >> H;
vector<Data> queries(W);
for (int i = 0; i < W; i++) {
queries[i] = i;
}
for (int i = 0; i < N; i++) {
ll a, b, x;
cin >> a >> b >> x;
x--;
op.push_back(Op{a, b, x});
}
Checker checker;
vector<int> ans;
ParallelBinarySearch(queries, checker, 0, N, ans);
ll a = 0;
ll b = 0;
for (int i = 0; i < W; i++) {
(ans[i] % 2 == 0 ? b : a)++;
}
show(ans);
cout << (a == b ? "DRAW" : a < b ? "B" : "A") << endl;
return 0;
}