#include "bits/stdc++.h" #ifdef WINT_MIN #define __MAI #endif using namespace std; typedef unsigned int uint; typedef long long int ll; typedef unsigned long long int ull; #define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<=l;--cnt) #define BIGINT 0x7FFFFFFF #define MD 1000000007ll #define PI 3.1415926535897932384626433832795 void printbit(int u) { if (u == 0)cout << 0; else { int s = 0, k = 0; for (; 0>= 1, k++)s = (s << 1) | (u & 1); for (; 0>= 1)cout << (s & 1); } }template ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } #define TIME chrono::system_clock::now() #define MILLISEC(t) (chrono::duration_cast(t).count()) namespace { std::chrono::system_clock::time_point t; void tic() { t = TIME; } void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - t)); } std::chrono::system_clock::time_point tle = TIME; #ifdef __MAI void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); } #else #define safe_tle(k) ; #endif } #ifndef __MAI namespace { class MaiScanner { public: template void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'>(int& var) { input_integer(var); return *this; } MaiScanner& operator>>(long long& var) { input_integer(var); return *this; } }; } MaiScanner scanner; #else #define scanner cin #endif template //using T = ll; class SegmentTree { public: struct IdxVal { int index; T value; inline IdxVal(int _i = 0, const T& _v = T()) :index(_i), value(_v) { } inline void set(int i, const T& v) { index = i; value = v; } inline bool operator<(const T& t) const { return value < t; } inline bool operator==(const T& t) const { return value == t; } inline bool operator<(const IdxVal& iv) const { return value < iv.value || (value == iv.value && index < iv.index); } inline bool operator==(const IdxVal& iv) const { return index == iv.index && value == iv.value; } }; struct Node { T sum, lazyValue; IdxVal max; bool isLazy; }; private: const int size_; vector leaf_data_; vector node_data_; T* leaf_; Node* node_; void _resize() { leaf_data_.resize(size_); node_data_.resize(size_ - 1); leaf_ = &leaf_data_[0]; node_ = &node_data_[0] - 1; } void _init() { for (int i = size_ - 1; 0 < i; --i) { int c = i << 1; if (size_ <= c) node_[i].max.set(c - size_, leaf_[c - size_]); else node_[i].max = node_[c].max; node_[i].isLazy = false; node_[i].sum = node_[i].lazyValue = 0; } } public: inline void fill(T val) { std::fill(leaf_data_.begin(), leaf_data_.end(), val); _init(); } SegmentTree(int _n) : size_([](int _n) {int s = 8; while (s < _n) s <<= 1; return s; }(_n)) { _resize(); _init(); } SegmentTree(int _n, const T& _fillVal) : size_([](int _n) {int s = 8; while (s < _n) s <<= 1; return s; }(_n)) { _resize(); fill(_fillVal); } private: // lazyを適応する // width: ptrが担当するnodeの範囲の大きさ(ptr = 1 ならば size_) inline void _applyDown(int ptr, int width) { width >>= 1; //if (size_ <= ptr) return; if (node_[ptr].isLazy) { node_[ptr].isLazy = false; int c = ptr << 1; if (size_ <= c) { leaf_[c - size_] += node_[ptr].lazyValue; leaf_[c + 1 - size_] += node_[ptr].lazyValue; } else { node_[c].sum += node_[ptr].lazyValue * width; node_[c].max.value += node_[ptr].lazyValue; node_[c].lazyValue += node_[ptr].lazyValue; node_[c].isLazy = true; node_[c + 1].sum += node_[ptr].lazyValue * width; node_[c + 1].max.value += node_[ptr].lazyValue; node_[c + 1].lazyValue += node_[ptr].lazyValue; node_[c + 1].isLazy = true; } node_[ptr].lazyValue = 0; } } // _downward_applyDown(ptr1): leaf[ptr1]の値を正しくする. void _downward_applyDown(int ptr1, int width = 1) { if (1 < ptr1) _downward_applyDown(ptr1 >> 1, width << 1); _applyDown(ptr1, width); } void _addValueRange(int begin, int end, T val, int ptr, int rangebegin, int rangeend) { if (rangeend <= begin || end <= rangebegin) return; // note:範囲外 if (begin <= rangebegin && rangeend <= end) { if (size_ <= ptr) { leaf_[rangebegin] += val; } else { node_[ptr].sum += val * (rangeend - rangebegin); node_[ptr].lazyValue += val; node_[ptr].isLazy = true; node_[ptr].max.value += val; } return; } _addValueRange(begin, end, val, ptr << 1, rangebegin, (rangebegin + rangeend) >> 1); _addValueRange(begin, end, val, (ptr << 1) + 1, (rangebegin + rangeend) >> 1, rangeend); node_[ptr].sum += val * (min(rangeend, end) - max(rangebegin, begin)); if (size_ <= ptr << 1) { int i = (ptr << 1) - size_; if (leaf_[i] < leaf_[i + 1]) node_[ptr].max.set(i + 1, leaf_[i + 1]); else node_[ptr].max.set(i, leaf_[i]); } else { if (node_[(ptr << 1)].max.value < node_[(ptr << 1) + 1].max.value) node_[ptr].max = node_[(ptr << 1) + 1].max; else node_[ptr].max = node_[(ptr << 1)].max; } } T _getSumRange(int begin, int end, int ptr, int rangebegin, int rangeend) { if (rangeend <= begin || end <= rangebegin) return 0; // note:範囲外 if (begin <= rangebegin && rangeend <= end) { if (size_ <= ptr) return leaf_[rangebegin]; else return node_[ptr].sum; } _applyDown(ptr, rangeend - rangebegin); return _getSumRange(begin, end, ptr << 1, rangebegin, (rangebegin + rangeend) >> 1) + _getSumRange(begin, end, (ptr << 1) + 1, (rangebegin + rangeend) >> 1, rangeend); } IdxVal _getMaxRange(int begin, int end, int ptr, int rangebegin, int rangeend) { if (rangeend <= begin || end <= rangebegin) return IdxVal(-1); // note:範囲外 if (begin <= rangebegin && rangeend <= end) { if (size_ <= ptr) return IdxVal(rangebegin, leaf_[rangebegin]); else return node_[ptr].max; } _applyDown(ptr, rangeend - rangebegin); auto l = _getMaxRange(begin, end, ptr << 1, rangebegin, (rangebegin + rangeend) >> 1); auto r = _getMaxRange(begin, end, (ptr << 1) + 1, (rangebegin + rangeend) >> 1, rangeend); if (l.index == -1) return move(r); if (r.index == -1) return move(l); return l.value < r.value ? move(r) : move(l); } public: // [index] の値を求める inline T getValue(int index) { _downward_applyDown((index + size_) >> 1); return leaf_[index]; } // 区間[begin,end)に一様にvalを加算する inline void addValueRange(int begin, int end, T val) { _addValueRange(begin, end, val, 1, 0, size_); } // 区間[begin,end)の和を求める inline T getSumRange(int begin, int end) { return _getSumRange(begin, end, 1, 0, size_); } // 区間[begin,end)の最大値とその位置を求める inline IdxVal getMaxRange(int begin, int end) { return _getMaxRange(begin, end, 1, 0, size_); } }; // https://yukicoder.me/submissions/170798 ll width, height; int m, n; int main() { int i, j, k; ll x, y, a, b; const ll smaaaaaaall = -2e18; scanner >> n >> width >> height; SegmentTree field(width); ll score_a, score_b; score_a = score_b = 0; repeat(n) { scanner >> a >> b >> x; --x; field.addValueRange(x, x + a, b); while (true) { auto p = field.getMaxRange(x, x + a); if (p.value >= height) { if ((cnt & 1) == 0) { score_a += 1; } else { score_b += 1; } field.addValueRange(p.index, p.index+1, smaaaaaaall); } else { break; } } } if (score_a == score_b) { cout << "DRAW" << endl; } else if (score_a < score_b) { cout << "B" << endl; } else { cout << "A" << endl; } return 0; }