結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
ユーザー mamekin
提出日時 2017-04-29 00:12:48
言語 C++14
(gcc 9.3.0)
結果
AC  
実行時間 152 ms
コード長 2,575 Byte
コンパイル時間 1,000 ms
使用メモリ 6,076 KB
最終ジャッジ日時 2020-01-24 08:39:44

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
00_sample1.txt AC 0 ms
3,312 KB
00_sample2.txt AC 0 ms
3,140 KB
00_sample3.txt AC 4 ms
3,296 KB
00_sample4.txt AC 4 ms
3,208 KB
00_sample5.txt AC 0 ms
3,204 KB
10_random_small1.txt AC 4 ms
3,308 KB
10_random_small2.txt AC 4 ms
3,280 KB
10_random_small3.txt AC 0 ms
3,208 KB
10_random_small4.txt AC 0 ms
3,292 KB
10_random_small5.txt AC 0 ms
3,300 KB
10_random_small6.txt AC 4 ms
3,196 KB
10_random_small7.txt AC 4 ms
3,220 KB
10_random_small8.txt AC 0 ms
3,272 KB
10_random_small9.txt AC 0 ms
3,280 KB
10_random_small10.txt AC 4 ms
3,280 KB
10_random_small11.txt AC 4 ms
3,300 KB
10_random_small12.txt AC 0 ms
3,204 KB
10_random_small13.txt AC 0 ms
3,296 KB
10_random_small14.txt AC 0 ms
3,296 KB
10_random_small15.txt AC 4 ms
3,304 KB
10_random_small16.txt AC 4 ms
3,220 KB
20_random_medium1.txt AC 4 ms
3,208 KB
20_random_medium2.txt AC 4 ms
3,256 KB
20_random_medium3.txt AC 4 ms
3,244 KB
20_random_medium4.txt AC 0 ms
3,168 KB
20_random_medium5.txt AC 4 ms
3,244 KB
20_random_medium6.txt AC 4 ms
3,332 KB
20_random_medium7.txt AC 4 ms
3,216 KB
20_random_medium8.txt AC 4 ms
3,240 KB
large4_gen_1.txt AC 124 ms
5,416 KB
large5_gen_1.txt AC 116 ms
5,120 KB
maxh_gen_1.txt AC 144 ms
5,960 KB
maxn15_gen_1.txt AC 140 ms
5,984 KB
maxn17_gen_1.txt AC 136 ms
5,988 KB
maxnw0_gen_1.txt AC 148 ms
6,076 KB
maxnw1_gen_1.txt AC 152 ms
5,956 KB
テストケース一括ダウンロード

ソースコード

diff #
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

class BinaryIndexedTree
{
private:
    int n;
    vector<long long> data;
public:
    BinaryIndexedTree(int n){ // コンストラクタ
        this->n = n;
        data.assign(n+1, 0);
    }
    void add(int k, long long x){ // k番目の要素にxを加算する
        ++ k;
        while(k <= n){
            data[k] += x;
            k += k & -k;
        }
    }
    long long sum(int k){ // 区間[0,k]の総和を返す
        ++ k;
        long long ret = 0;
        while(k > 0){
            ret += data[k];
            k -= k & -k;
        }
        return ret;
    }
    long long sum(int a, int b){ // 区間[a,b]の総和を返す
        return sum(b) - sum(a-1);
    }
    int upper_bound(long long x){ // 総和が初めてxを超える位置を返す(ただし、各位置の数値が非負数であることを前提とする)
        int b = 1;
        while(b < n)
            b *= 2;
        int a = 0;
        while(b > 0){
            if(a+b <= n && x >= data[a+b]){
                x -= data[a+b];
                a += b;
            }
            b /= 2;
        }
        return (a < n)? a : -1;
    }
    int lower_bound(long long x){ // 総和が初めてx以上になる位置を返す(ただし、各位置の数値が非負数であることを前提とする)
        return upper_bound(x-1);
    }
};

int main()
{
    int n, w;
    long long h;
    cin >> n >> w >> h;

    vector<tuple<int, int, int> > v(2*n);
    for(int i=0; i<n; ++i){
        int a, b, x;
        cin >> a >> b >> x;
        v[2*i]   = make_tuple(x-1, i, b);
        v[2*i+1] = make_tuple(x-1+a, i, -b);
    }
    sort(v.begin(), v.end());

    BinaryIndexedTree bit(n);
    int k = 0;
    int cnt = 0;
    for(int x=0; x<w; ++x){
        while(k < 2 * n && get<0>(v[k]) == x){
            bit.add(get<1>(v[k]), get<2>(v[k]));
            ++ k;
        }
        int i = bit.lower_bound(h);
        if(i % 2 == 0)
            ++ cnt; 
    }

    if(cnt > w - cnt)
        cout << 'A' << endl;
    else if(cnt == w - cnt)
        cout << "DRAW" << endl;
    else
        cout << 'B' << endl;

    return 0;
}
0