結果
問題 | No.511 落ちゲー 〜手作業のぬくもり〜 |
ユーザー | LayCurse |
提出日時 | 2017-04-30 01:02:30 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 196 ms / 4,000 ms |
コード長 | 8,291 bytes |
コンパイル時間 | 1,354 ms |
コンパイル使用メモリ | 163,136 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-11-24 12:40:34 |
合計ジャッジ時間 | 3,761 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 1 ms
5,248 KB |
testcase_11 | AC | 1 ms
5,248 KB |
testcase_12 | AC | 1 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 1 ms
5,248 KB |
testcase_16 | AC | 1 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 1 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 1 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 1 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 3 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 195 ms
10,752 KB |
testcase_30 | AC | 169 ms
10,624 KB |
testcase_31 | AC | 153 ms
10,624 KB |
testcase_32 | AC | 151 ms
10,880 KB |
testcase_33 | AC | 115 ms
6,272 KB |
testcase_34 | AC | 101 ms
5,376 KB |
testcase_35 | AC | 196 ms
10,752 KB |
testcase_36 | AC | 191 ms
10,880 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; void rd(int &x){ int k, m=0; x=0; for(;;){ k = getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } void rd(long long &x){ int k, m=0; x=0; for(;;){ k = getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } void wt_L(const char c[]){ int i=0; for(i=0;c[i]!='\0';i++){ putchar_unlocked(c[i]); } } template<class S, class T> inline void chmin(S &a, T b){ if(a>b){ a=b; } } template<class T> struct segtree{ T *addval, *fixval, *mn, *sum; char *fixed; int N, logN, *mnind; void malloc(int maxN, int once = 0){ int i; for(i=1;i<maxN;i*=2){ ; } sum = (T*)std::malloc(sizeof(T)*2*i); mn = (T*)std::malloc(sizeof(T)*2*i); mnind = (int*)std::malloc(sizeof(T)*2*i); fixval = (T*)std::malloc(sizeof(T)*i); addval = (T*)std::malloc(sizeof(T)*i); fixed = (char*)std::malloc(sizeof(char)*i); if(once){ setN(maxN); } } void free(void){ std::free(sum); std::free(mn); std::free(mnind); std::free(fixval); std::free(addval); std::free(fixed); } T& operator[](int i){ return sum[N+i]; } void setN(int n, int zerofill = 1, int dobuild = 1){ int i; for(i=1,logN=0;i<n;i*=2,logN++){ ; } N = i; if(zerofill){ for(i=0;i<N;i++){ sum[N+i] = 0; } } if(dobuild){ build(); } } void build(void){ int i; for(i=0;i<N;i++){ mn[N+i] = sum[N+i]; mnind[N+i] = i; } for(i=N-1;i;i--){ sum[i] = sum[2*i] + sum[2*i+1]; if(mn[2*i] <= mn[2*i+1]){ mn[i] = mn[2*i]; mnind[i] = mnind[2*i]; } else{ mn[i] = mn[2*i+1]; mnind[i] = mnind[2*i+1]; } } for(i=1;i<N;i++){ fixed[i] = 0; } for(i=1;i<N;i++){ addval[i] = 0; } } inline void push_one(int a, int sz, int st){ if(fixed[a]){ if(sz > 1){ fixed[a*2] = fixed[a*2+1] = 1; fixval[a*2] = fixval[a*2+1] = fixval[a]; sum[a*2] = sum[a*2+1] = sz * fixval[a]; mn[a*2] = mn[a*2+1] = fixval[a]; mnind[a*2] = st; mnind[a*2+1] = st + sz; } else{ sum[a*2] = sum[a*2+1] = sz * fixval[a]; mn[a*2] = mn[a*2+1] = fixval[a]; mnind[a*2] = st; mnind[a*2+1] = st + sz; } fixed[a] = 0; addval[a] = 0; return; } if(addval[a] != 0){ if(sz > 1){ if(fixed[a*2]){ fixval[a*2] += addval[a]; } else{ addval[a*2] += addval[a]; } if(fixed[a*2+1]){ fixval[a*2+1] += addval[a]; } else{ addval[a*2+1] += addval[a]; } sum[a*2] += sz * addval[a]; sum[a*2+1] += sz * addval[a]; mn[a*2] += addval[a]; mn[a*2+1] += addval[a]; } else{ sum[a*2] += sz * addval[a]; sum[a*2+1] += sz * addval[a]; mn[a*2] += addval[a]; mn[a*2+1] += addval[a]; } addval[a] = 0; return; } } inline void push(int a){ int aa=a - N, i, nd, st, sz; for(i=logN;i;i--){ nd = a>>i; sz = 1<<(i-1); st = 2 * sz * (aa>>i); push_one(nd, sz, st); } } inline void build(int a){ int st=a - N, sz=1; while(a > 1){ if(a%2){ st += sz; } a /= 2; sz *= 2; if(fixed[a]){ sum[a] = sz * fixval[a]; mn[a] = fixval[a]; } else{ sum[a] = sum[a*2] + sum[a*2+1]; if(mn[a*2] <= mn[a*2+1]){ mn[a] = mn[a*2]; mnind[a] = mnind[a*2]; } else{ mn[a] = mn[a*2+1]; mnind[a] = mnind[a*2+1]; } if(addval[a] != 0){ mn[a] += addval[a]; sum[a] += sz * addval[a]; } } } } inline void change(int a, int b, T val){ int aa, bb, st_a=a, st_b=b, sz=1; if(a >= b){ return; } aa = (a += N); bb = (b += N); push(a); push(b-1); if(a%2){ sum[a] = mn[a] = val; a++; st_a += sz; } if(b%2){ b--; st_b -= sz; sum[b] = mn[b] = val; } a /= 2; b /= 2; while(a < b){ sz *= 2; if(a%2){ fixed[a]=1; fixval[a]=val; sum[a] = sz * val; mn[a] = val; mnind[a] = st_a; a++; st_a += sz; } if(b%2){ b--; st_b -= sz; fixed[b]=1; fixval[b]=val; sum[b] = sz * val; mn[b] = val; mnind[b] = st_b; } a /= 2; b /= 2; } build(aa); build(bb-1); } inline void add(int a, int b, T val){ int aa, bb, sz=1; if(a >= b){ return; } aa = (a += N); bb = (b += N); push(a); push(b-1); if(a%2){ sum[a] += val; mn[a] += val; a++; } if(b%2){ b--; sum[b] += val; mn[b] += val; } a /= 2; b /= 2; while(a < b){ sz *= 2; if(a%2){ if(fixed[a]){ fixval[a] += val; } else{ addval[a] += val; } sum[a] += sz * val; mn[a] += val; a++; } if(b%2){ b--; if(fixed[b]){ fixval[b] += val; } else{ addval[b] += val; } sum[b] += sz * val; mn[b] += val; } a /= 2; b /= 2; } build(aa); build(bb-1); } inline pair<T,int> getMin(int a, int b){ int sz=1; pair<T,int> res; a += N; b += N; push(a); push(b-1); res.first = numeric_limits<T>::max(); res.second = -1; while(a < b){ if(a%2){ chmin(res, make_pair(mn[a], mnind[a])); a++; } if(b%2){ b--; chmin(res, make_pair(mn[b], mnind[b])); } a /= 2; b /= 2; } return res; } inline T getMinVal(int a, int b){ return getMin(a,b).first; } inline T getMinInd(int a, int b){ return getMin(a,b).second; } inline T getSum(int a, int b){ T res; int sz=1; a += N; b += N; push(a); push(b-1); res = 0; while(a < b){ if(a%2){ res += sum[a++]; } if(b%2){ res += sum[--b]; } a /= 2; b /= 2; } return res; } } ; int A[100000], B[100000], X[100000]; int main(){ int i, k; long long H, N, W, res[2]={0LL, 0LL}; pair<long long,int> mn; segtree<long long> t; rd(N); rd(W); rd(H); { int Lj4PdHRW; for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){ rd(A[Lj4PdHRW]); rd(B[Lj4PdHRW]); rd(X[Lj4PdHRW]); } } { int KL2GvlyY; for(KL2GvlyY= 0;KL2GvlyY< (N-1) + 1;KL2GvlyY++){ X[KL2GvlyY]--; } } t.malloc(W, 1); for(i=0;i<N;i++){ t.add(X[i], X[i]+A[i], -B[i]); for(;;){ mn = t.getMin(X[i], X[i]+A[i]); if(mn.first > -H){ break; } k = mn.second; res[i%2]++; t.add(k,k+1,1000000000000000000LL); } } if(res[0] > res[1]){ wt_L("A"); putchar_unlocked('\n'); } if(res[0] < res[1]){ wt_L("B"); putchar_unlocked('\n'); } if(res[0]==res[1]){ wt_L("DRAW"); putchar_unlocked('\n'); } return 0; } // cLay varsion 20170430-1 // --- original code --- // int A[100000], B[100000], X[100000]; // { // int i, k; // ll N, W, H; // segtree<ll> t; // pair<ll,int> mn; // ll res[2] = {0LL, 0LL}; // // rd(N,W,H,(A,B,X)(N)); // X[0..N-1]--; // // t.malloc(W, 1); // // rep(i,N){ // t.add(X[i], X[i]+A[i], -B[i]); // for(;;){ // mn = t.getMin(X[i], X[i]+A[i]); // if(mn.first > -H) break; // k = mn.second; // res[i%2]++; // t.add(k,k+1,1d18); // } // } // // if(res[0] > res[1]) wt("A"); // if(res[0] < res[1]) wt("B"); // if(res[0]==res[1]) wt("DRAW"); // }