結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
ユーザー anta
提出日時 2018-04-06 19:30:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 99 ms / 4,000 ms
コード長 5,241 bytes
コンパイル時間 1,995 ms
コンパイル使用メモリ 187,616 KB
実行使用メモリ 11,604 KB
最終ジャッジ日時 2024-11-24 12:42:04
合計ジャッジ時間 3,789 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
using Val = ll;
const Val infVal = INFL;
struct Sum {
    int num;
    Val minVal;
    Sum() : num(0), minVal(infVal) {}
    Sum(const Val &val, int pos) : num(val == infVal ? 0 : 1), minVal(val) { }
    Sum &operator+=(const Sum &that) {
        num += that.num;
        amin(minVal, that.minVal);
        return *this;
    }
    Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};
struct Add {
    ll sub;
    Add() : sub(0) { }
    Add &operator+=(const Add &that) { sub += that.sub; return *this; }
    void addToVal(Val &val, int pos) const { if (val != infVal) val -= sub; }
    void addToSum(Sum &sum, int left, int right) const {
        if (sum.minVal != infVal)
            sum.minVal -= sub;
    }
};
struct SegmentTree {
    vector<Val> leafs;
    vector<Sum> nodes;
    vector<Add> add;
    vector<int> leftpos, rightpos;
    int n, n2;
    void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
    void init(const vector<Val> &u) {
        n = 1; while (n < (int)u.size()) n *= 2;
        n2 = (n - 1) / 2 + 1;
        leafs = u; leafs.resize(n, Val());
        nodes.resize(n);
        for (int i = n - 1; i >= n2; -- i)
            nodes[i] = Sum(leafs[i * 2 - n], i * 2 - n) + Sum(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
        for (int i = n2 - 1; i > 0; -- i)
            nodes[i] = nodes[i * 2] + nodes[i * 2 + 1];
        add.assign(n, Add());
        leftpos.resize(n); rightpos.resize(n);
        for (int i = n - 1; i >= n2; -- i) {
            leftpos[i] = i * 2 - n;
            rightpos[i] = (i * 2 + 1 - n) + 1;
        }
        for (int i = n2 - 1; i > 0; -- i) {
            leftpos[i] = leftpos[i * 2];
            rightpos[i] = rightpos[i * 2 + 1];
        }
    }
    Val get(int i) {
        int indices[128];
        int k = getIndices(indices, i, i + 1);
        propagateRange(indices, k);
        return leafs[i];
    }
    Sum getRangeCommutative(int i, int j) {
        int indices[128];
        int k = getIndices(indices, i, j);
        propagateRange(indices, k);
        Sum res = Sum();
        for (int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += sum(l ++);
            if (r & 1) res += sum(-- r);
        }
        return res;
    }
    void set(int i, const Val &x) {
        int indices[128];
        int k = getIndices(indices, i, i + 1);
        propagateRange(indices, k);
        leafs[i] = x;
        mergeRange(indices, k);
    }
    void addToRange(int i, int j, const Add &x) {
        if (i >= j) return;
        int indices[128];
        int k = getIndices(indices, i, j);
        propagateRange(indices, k);
        int l = i + n, r = j + n;
        if (l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }
        if (r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }
        for (l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) add[l ++] += x;
            if (r & 1) add[-- r] += x;
        }
        mergeRange(indices, k);
    }
private:
    int getIndices(int indices[], int i, int j) const {
        int k = 0, l, r;
        if (i >= j) return 0;
        for (l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {
            indices[k ++] = l;
            indices[k ++] = r;
        }
        for (; l; l >>= 1) indices[k ++] = l;
        return k;
    }
    void propagateRange(int indices[], int k) {
        for (int i = k - 1; i >= 0; -- i)
            propagate(indices[i]);
    }
    void mergeRange(int indices[], int k) {
        for (int i = 0; i < k; ++ i)
            merge(indices[i]);
    }
    inline void propagate(int i) {
        if (i >= n) return;
        add[i].addToSum(nodes[i], leftpos[i], rightpos[i]);
        if (i * 2 < n) {
            add[i * 2] += add[i];
            add[i * 2 + 1] += add[i];
        } else {
            add[i].addToVal(leafs[i * 2 - n], i * 2 - n);
            add[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
        }
        add[i] = Add();
    }
    inline void merge(int i) {
        if (i >= n) return;
        nodes[i] = sum(i * 2) + sum(i * 2 + 1);
    }
    inline Sum sum(int i) {
        propagate(i);
        return i < n ? nodes[i] : Sum(leafs[i - n], i - n);
    }
public:
    void searchAndSetInf(int i, int j, vector<pair<int, Val>> &out) {
        searchAndSetInfAllRec(1, i, j, out);
    }
private:
    void searchAndSetInfAllRec(int i, int l, int r, vector<pair<int, Val>> &out) {
        propagate(i);
        if (sum(i).minVal > 0) return;
        if (i >= n) {
            if (l <= i - n && i - n < r) {
                out.emplace_back(i - n, leafs[i - n]);
                leafs[i - n] = infVal;
            }
            return;
        }
        amax(l, leftpos[i]);
        amin(r, rightpos[i]);
        if (l >= r) return;
        searchAndSetInfAllRec(i * 2, l, r, out);
        searchAndSetInfAllRec(i * 2 + 1, l, r, out);
        merge(i);
    }
};
int main() {
    int N; int W; long long H;
    while (~scanf("%d%d%lld", &N, &W, &H)) {
        SegmentTree segt;
        segt.init(W, Val(H));
        vector<pair<int, Val>> tmp;
        array<int, 2> score = {0, 0};
        rep(i, N) {
            int a; long long b; int x;
            scanf("%d%lld%d", &a, &b, &x), -- x;
            Add add;
            add.sub = b;
            segt.addToRange(x, x + a, add);
            tmp.clear();
            segt.searchAndSetInf(x, x + a, tmp);
            score[i % 2] += (int)tmp.size();
        }
        puts(score[0] > score[1] ? "A" : score[0] < score[1] ? "B" : "DRAW");
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0