結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
ユーザー drken1215drken1215
提出日時 2017-12-08 02:30:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 154 ms / 4,000 ms
コード長 5,682 bytes
コンパイル時間 3,167 ms
コンパイル使用メモリ 107,388 KB
実行使用メモリ 13,956 KB
最終ジャッジ日時 2023-08-16 03:09:23
合計ジャッジ時間 3,538 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
11,608 KB
testcase_01 AC 3 ms
11,624 KB
testcase_02 AC 4 ms
11,644 KB
testcase_03 AC 4 ms
11,612 KB
testcase_04 AC 4 ms
11,596 KB
testcase_05 AC 4 ms
11,708 KB
testcase_06 AC 4 ms
11,732 KB
testcase_07 AC 3 ms
11,696 KB
testcase_08 AC 3 ms
11,656 KB
testcase_09 AC 3 ms
11,728 KB
testcase_10 AC 3 ms
11,640 KB
testcase_11 AC 3 ms
11,848 KB
testcase_12 AC 3 ms
11,896 KB
testcase_13 AC 3 ms
11,776 KB
testcase_14 AC 4 ms
11,700 KB
testcase_15 AC 4 ms
11,888 KB
testcase_16 AC 4 ms
11,772 KB
testcase_17 AC 3 ms
11,648 KB
testcase_18 AC 4 ms
11,592 KB
testcase_19 AC 3 ms
11,596 KB
testcase_20 AC 3 ms
11,676 KB
testcase_21 AC 4 ms
11,904 KB
testcase_22 AC 4 ms
11,608 KB
testcase_23 AC 5 ms
11,640 KB
testcase_24 AC 4 ms
11,648 KB
testcase_25 AC 5 ms
11,672 KB
testcase_26 AC 4 ms
11,660 KB
testcase_27 AC 4 ms
11,584 KB
testcase_28 AC 4 ms
11,752 KB
testcase_29 AC 153 ms
13,656 KB
testcase_30 AC 148 ms
13,640 KB
testcase_31 AC 142 ms
13,632 KB
testcase_32 AC 107 ms
13,956 KB
testcase_33 AC 112 ms
11,700 KB
testcase_34 AC 98 ms
11,700 KB
testcase_35 AC 152 ms
13,632 KB
testcase_36 AC 154 ms
13,712 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

const int MAX = 110000;



const long long INF = 1LL<<59;
const int MAX_N = MAX;

typedef long long VAL;              // MAX
typedef long long DELAY;            // add

const VAL UNITY_VAL = -INF;
const DELAY UNITY_DELAY = 0;

int SIZE_SEG;
struct SegTree {
    pair<VAL,int> val[4*MAX_N];        // min
    DELAY delay[4*MAX_N];    // +
    
    void init(int n = MAX_N, VAL v = UNITY_VAL, DELAY dv = UNITY_DELAY) {
        SIZE_SEG = 1;
        while (SIZE_SEG < n) SIZE_SEG *= 2;
        for (int i = 0; i < 2*SIZE_SEG-1; ++i) val[i] = make_pair(v, -1), delay[i] = dv;
    }
    
    inline void init_set(int a, VAL x) {
        int k = a + SIZE_SEG-1;
        val[k] = make_pair(x, a);
    }
    
    inline void init_tree(int k = 0, int l = 0, int r = SIZE_SEG) {
        if (r - l == 1) {}                      // leaf
        else {
            init_tree(k*2+1, l, (l+r)/2);
            init_tree(k*2+2, (l+r)/2, r);
            val[k] = merge(val[k*2+1], val[k*2+2]);
        }
    }
    
    inline pair<VAL,int> merge(pair<VAL,int> a, pair<VAL,int> b) {
        pair<VAL,int> res = make_pair(UNITY_VAL, -1);
        chmax(res, a);
        chmax(res, b);
        // res.f = a.f + b.f;
        return res;
    }
    
    inline void add(DELAY &d, DELAY x) {
        d += x;
        // d.f += x.f;
    }
    
    inline void reflect(pair<VAL,int> &a, DELAY d, int l, int r) {
        a.first += d;
        // a.f += d.f * (r-l);
    }
    
    inline void redelay(int k, int l, int r) {
        reflect(val[k], delay[k], l, r);
        if (k < SIZE_SEG-1) {
            add(delay[k*2+1], delay[k]);
            add(delay[k*2+2], delay[k]);
        }
        delay[k] = UNITY_DELAY;
    }
    
    inline void renode(int k, int l, int r) {
        val[k] = merge(val[k*2+1], val[k*2+2]);
    }
    
    inline void set(int a, int b, DELAY x, int k = 0, int l = 0, int r = SIZE_SEG) {
        if (a <= l && r <= b) {                 // included
            add(delay[k], x);
            redelay(k, l, r);
        }
        else if (a < r && l < b) {              // intersected
            redelay(k, l, r);
            set(a, b, x, k*2+1, l, (l+r)/2);
            set(a, b, x, k*2+2, (l+r)/2, r);
            renode(k, l, r);
        }
        else {                                  // no-intersected
            redelay(k, l, r);
        }
    }
    
    inline pair<VAL,int> get(int a, int b, int k = 0, int l = 0, int r = SIZE_SEG) {
        redelay(k, l, r);
        if (a <= l && r <= b) {                 // included
            return val[k];
        }
        else if (a < r && l < b) {              // intersected
            pair<VAL,int> t1 = get(a, b, k*2+1, l, (l+r)/2);
            pair<VAL,int> t2 = get(a, b, k*2+2, (l+r)/2, r);
            renode(k, l, r);
            
            return merge(t1, t2);
        }
        else {                                  // no-intersected
            return make_pair(UNITY_VAL, -1);
        }
    }
    
    inline pair<VAL,int> operator [] (int i) {return get(i, i+1);}
    
    void print(long long r = SIZE_SEG) {
        long long t = 2;
        for (int i = 0; i < r*2-1; ++i) {
            cout << make_pair(val[i], delay[i]) << ",";
            if (i == t-2) {cout << endl; t *= 2;}
        }
        for (int i = 0; i < r; ++i) {
            cout << get(i, i+1) << ", ";
        }
        cout << endl << endl;
    }
} seg;



int N, W;
long long H;

int main() {
    while (cin >> N >> W >> H) {
        seg.init(W + 5);
        for (int i = 0; i < W; ++i) seg.init_set(i, 0);
        seg.init_tree();
        
        int res = 0;
        for (int i = 0; i < N; ++i) {
            int a, b, x;
            scanf("%d %d %d", &a, &b, &x);
            --x;
            int left = x, right = x + a;
            long long add = b;
            
            seg.set(left, right, add);
            while (true) {
                pair<VAL,int> p = seg.get(0, W);
                
                //COUT(i); seg.print(); COUT(p); cout << endl << endl;
                
                if (p.first < H) break;
                if (i % 2 == 0) ++res;
                seg.set(p.second, p.second + 1, -INF);
            }
        }
        
        if (res > W-res) puts("A");
        else if (res < W-res) puts("B");
        else puts("DRAW");
    }
}
0