結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
コンテスト
ユーザー ふーらくたる
提出日時 2017-12-18 22:24:42
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,884 ms / 4,000 ms
コード長 3,647 bytes
コンパイル時間 1,140 ms
コンパイル使用メモリ 75,716 KB
実行使用メモリ 12,752 KB
最終ジャッジ日時 2024-11-24 12:42:00
合計ジャッジ時間 9,765 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define int long long

// Range Sum Query and Range Add Query
template <typename T>
struct LazySegmentTree {
    const T DEFULT_VAL = 0;

    vector<T> dat;
    vector<T> lazy;
    int end;

    LazySegmentTree(vector<T>& d) {
        int n = d.size();
        end = 1;
        while (end < n) end *= 2;

        dat.resize(2 * end - 1, DEFULT_VAL);
        lazy.resize(2 * end - 1, 0);

        for (int i = 0; i < d.size(); i++) {
            dat[i + end - 1] = d[i];
        }
        for (int i = end - 2; i >= 0; i--) {
            dat[i] = dat[2 * i + 1] + dat[2 * i + 2];
        }
    }

    void inline eval(int id, int node_lb, int node_ub) {
        if (lazy[id] != 0) {    // 伝搬するべき値がある
            dat[id] += lazy[id];

            if (node_ub - node_lb > 1) {
                lazy[2 * id + 1] += lazy[id] / 2;
                lazy[2 * id + 2] += lazy[id] / 2;
            }

            lazy[id] = 0;
        }
    }

    void inline add(int lb, int ub, T a) {
        add(lb, ub, a, 0, 0, end);
    }

    void inline add(int lb, int ub, T a, int id, int node_lb, int node_ub) {
        eval(id, node_lb, node_ub);

        if (node_ub <= lb || ub <= node_lb) { return; }

        if (lb <= node_lb && node_ub <= ub) {
            lazy[id] += (node_ub - node_lb) * a;
            eval(id, node_lb, node_ub);
        } else {
            add(lb, ub, a, id * 2 + 1, node_lb, (node_lb + node_ub) / 2);
            add(lb, ub, a, id * 2 + 2, (node_lb + node_ub) / 2, node_ub);
            dat[id] = dat[2 * id + 1] + dat[2 * id + 2];
        }
    }

    T inline query(int idx) {
        return query(idx, idx + 1);
    }

    T inline query(int lb, int ub) {
        return query(lb, ub, 0, 0, end);
    }

    T inline query(int lb, int ub, int id, int node_lb, int node_ub) {
        eval(id, node_lb, node_ub);

        if (node_ub <= lb || ub <= node_lb) { return DEFULT_VAL; }

        if (lb <= node_lb && node_ub <= ub) { return dat[id]; }
        else {
            T  vl = query(lb, ub, id * 2 + 1, node_lb, (node_lb + node_ub) / 2),
               vr = query(lb, ub, id * 2 + 2, (node_lb + node_ub) / 2, node_ub);
            return vl + vr;
        }
    }
};

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, w, h;
    cin >> n >> w >> h;

    vector<int> a(n), b(n), x(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> x[i];
        x[i]--;
    }

    vector<int> ng(w), ok(w);   // 各x_iごとに得点が得られたクエリ番号を二分探索
    vector<int> id(w);
    for (int i = 0; i < w; i++) {
        ng[i] = -1;
        ok[i] = n + 1;

        id[i] = i;
    }

    // 並列二分探索
    for (int loop = 0; loop < 20; loop++) {
        sort(id.begin(), id.end(), [&](int i, int j) {
            return (ng[i] + ok[i]) / 2 < (ng[j] + ok[j]) / 2;
        });
        vector<int> blocks(w, 0);
        LazySegmentTree<int> segtree(blocks);

        int ptr = 0;
        for (int i : id) {
            int mid = (ng[i] + ok[i]) / 2;
            while (ptr <= min(n - 1, mid)) {
                segtree.add(x[ptr], x[ptr] + a[ptr], b[ptr]);
                ptr++;
            }
            if (segtree.query(i) >= h) ok[i] = mid;
            else ng[i] = mid;
        }
    }

    int A = 0;
    int B = 0;
    for (int i = 0; i < w; i++) {
        if (ok[i] > n) continue;
        if (ok[i] % 2 == 0) A++;
        else B++;
    }

    if (A > B) cout << "A" << endl;
    else if (A == B) cout << "DRAW" << endl;
    else cout << "B" << endl;

    return 0;
}
0