結果
問題 | No.511 落ちゲー 〜手作業のぬくもり〜 |
ユーザー | mai |
提出日時 | 2017-05-04 11:51:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,589 bytes |
コンパイル時間 | 2,556 ms |
コンパイル使用メモリ | 217,192 KB |
実行使用メモリ | 14,764 KB |
最終ジャッジ日時 | 2024-09-14 07:00:01 |
合計ジャッジ時間 | 6,370 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
14,604 KB |
testcase_01 | AC | 9 ms
14,508 KB |
testcase_02 | AC | 9 ms
14,672 KB |
testcase_03 | AC | 9 ms
14,624 KB |
testcase_04 | AC | 8 ms
14,660 KB |
testcase_05 | AC | 9 ms
14,764 KB |
testcase_06 | AC | 9 ms
14,620 KB |
testcase_07 | AC | 6 ms
14,600 KB |
testcase_08 | AC | 9 ms
14,508 KB |
testcase_09 | AC | 9 ms
14,576 KB |
testcase_10 | AC | 8 ms
14,592 KB |
testcase_11 | AC | 9 ms
14,444 KB |
testcase_12 | AC | 8 ms
14,676 KB |
testcase_13 | AC | 9 ms
14,560 KB |
testcase_14 | AC | 9 ms
14,576 KB |
testcase_15 | AC | 9 ms
14,612 KB |
testcase_16 | AC | 9 ms
14,592 KB |
testcase_17 | AC | 8 ms
14,604 KB |
testcase_18 | AC | 9 ms
14,432 KB |
testcase_19 | AC | 9 ms
14,592 KB |
testcase_20 | AC | 8 ms
14,628 KB |
testcase_21 | AC | 10 ms
14,712 KB |
testcase_22 | AC | 11 ms
14,652 KB |
testcase_23 | AC | 10 ms
14,660 KB |
testcase_24 | AC | 9 ms
14,616 KB |
testcase_25 | AC | 10 ms
14,672 KB |
testcase_26 | AC | 10 ms
14,560 KB |
testcase_27 | AC | 11 ms
14,640 KB |
testcase_28 | AC | 11 ms
14,600 KB |
testcase_29 | AC | 378 ms
14,564 KB |
testcase_30 | AC | 323 ms
14,612 KB |
testcase_31 | AC | 290 ms
14,600 KB |
testcase_32 | WA | - |
testcase_33 | AC | 269 ms
14,600 KB |
testcase_34 | AC | 236 ms
14,604 KB |
testcase_35 | AC | 374 ms
14,668 KB |
testcase_36 | AC | 371 ms
14,620 KB |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:235:28: warning: overflow in conversion from 'double' to 'll' {aka 'long long int'} changes value from '-9.9999999999999997e+98' to '-9223372036854775808' [-Woverflow] 235 | const ll smaaaaaaall = -1e99; | ^~~~~
ソースコード
#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<<e<<" ";}cout<<endl; #define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;} #define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl; #define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;} #define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;} #define ALL(v) (v).begin(),(v).end() #define repeat(l) for(auto cnt=0;cnt<(l);++cnt) #define upto(l,r) for(auto cnt=l;cnt<=r;++cnt) #define downto(r,l) for(auti cnt=r;cnt>=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<u; u >>= 1, k++)s = (s << 1) | (u & 1); for (; 0<k--; s >>= 1)cout << (s & 1); } }template<typename T1, typename T2> ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; } #define TIME chrono::system_clock::now() #define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(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<typename T> void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'<cc; cc = getchar_unlocked()) if (cc == '-') sign = -1; for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked()) var = (var << 3) + (var << 1) + cc - '0'; var = var*sign; } void ign() { getchar_unlocked(); } MaiScanner& operator>>(int& var) { input_integer<int>(var); return *this; } MaiScanner& operator>>(long long& var) { input_integer<long long>(var); return *this; } }; } MaiScanner scanner; #else #define scanner cin #endif template<typename T> //typedef int T; class segtree { int size; public: struct VI { T val; int idx; VI(T val = 0,int idx = 0):val(val),idx(idx){} static const VI& max (const VI& a, const VI& b) { return a.val == b.val ? (a.idx < b.idx ? a : b) : (a.val >= b.val ? a : b); } static const VI& min(const VI& a, const VI& b) { return a.val == b.val ? (a.idx < b.idx ? a : b) : (a.val <= b.val ? a : b); } bool operator==(const VI& e) const { return val == e.val && idx == e.idx; } bool operator<(const VI& e) const { return (val < e.val) || (idx > e.idx); } }; private: vector<int> mark; vector<T> single; // max(min)遅延伝搬用 vector<pair<T, T>> addtree; // sum,lazy vector<VI> maxtree; // val,idx public: segtree(int n) { size = 8; while (size < n) size <<= 1; addtree.resize(size * 2); mark.resize(size * 2); single.resize(size * 2); maxtree.resize(size * 2); _flat(); } void _flat() { for (int i = 0; i < size; ++i) { maxtree[i + size - 1] = VI(0, i); } for (int i = size - 2; 0 <= i; --i) { int c = 2 * i + 1; maxtree[i] = maxtree[c]; } } // 区間[begin,end)に一様にvalを加算する void addvalrange(int begin, int end, T val, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return; // note:範囲外 if (begin <= rangebegin && rangeend <= end) { addtree[ptr].first += val * (rangeend - rangebegin); addtree[ptr].second += val * (rangeend - rangebegin) / 2; mark[ptr] |= 3; maxtree[ptr].val += val; single[ptr] += val; if (rangeend - rangebegin > 1) { // せっかくだから _applyDown(ptr); } return; } _applyDown(ptr); // TODO:いる? int rangemid = (rangebegin + rangeend) / 2; addvalrange(begin, end, val, ptr * 2 + 1, rangebegin, rangemid); addvalrange(begin, end, val, ptr * 2 + 2, rangemid, rangeend); addtree[ptr].first += val * (min(rangeend, end) - max(rangebegin, begin)); maxtree[ptr] = max(maxtree[ptr * 2 + 1], maxtree[ptr * 2 + 2]); // インデックスもmaxを選択する点に注意 } inline void _applyDown(int ptr) { //if (size - 1 <= ptr) return; if (mark[ptr] & 1) { mark[ptr] ^= 1; int c1 = ptr * 2 + 1; int c2 = ptr * 2 + 2; addtree[c1].first += addtree[ptr].second; addtree[c1].second += addtree[ptr].second / 2; mark[c1] |= 1; addtree[c2].first += addtree[ptr].second; addtree[c2].second += addtree[ptr].second / 2; mark[c2] |= 1; addtree[ptr].second = 0; } if (mark[ptr] & 2) { mark[ptr] ^= 2; int c1 = ptr * 2 + 1; int c2 = ptr * 2 + 2; maxtree[c1].val += single[ptr]; single[c1] += single[ptr]; mark[c1] |= 2; maxtree[c2].val += single[ptr]; single[c2] += single[ptr]; mark[c2] |= 2; single[ptr] = 0; } } inline void _downward_applyDown(int ptr1) { if (1 < ptr1) _downward_applyDown(ptr1 >> 1); _applyDown(ptr1 - 1); } T getval(int index) { T sum = 0; _downward_applyDown((index + size) >> 1); return addtree[index + size - 1].first; } T getsumrange(int begin, int end, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return 0; // note:範囲外 if (begin <= rangebegin && rangeend <= end) return addtree[ptr].first; _applyDown(ptr); int rangemid = (rangebegin + rangeend) / 2; return getsumrange(begin, end, ptr * 2 + 1, rangebegin, rangemid) + getsumrange(begin, end, ptr * 2 + 2, rangemid, rangeend); } VI getmaxrange(int begin, int end, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return VI(0, -1); // note:範囲外 if (begin <= rangebegin && rangeend <= end) return maxtree[ptr]; _applyDown(ptr); int rangemid = (rangebegin + rangeend) / 2; VI l = getmaxrange(begin, end, ptr * 2 + 1, rangebegin, rangemid); VI r = getmaxrange(begin, end, ptr * 2 + 2, rangemid, rangeend); if (l.idx == -1) return r; if (r.idx == -1) return l; return VI::max(l, r); // インデックスもmaxを選択する点に注意 } }; int width, height; int m, n; int main() { int i, j, k; ll x, y, a, b; segtree<ll> field(100000); const ll smaaaaaaall = -1e99; scanner >> n >> width >> height; ll score_a, score_b; score_a = score_b = 0; repeat(n) { scanner >> a >> b >> x; field.addvalrange(x, x + a, b); while (true) { auto p = field.getmaxrange(x, x + a); if (p.val >= height) { if (cnt % 2 == 0) { score_a += 1; } else { score_b += 1; } field.addvalrange(p.idx, p.idx+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; }