結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
ユーザー LayCurseLayCurse
提出日時 2017-04-28 23:37:13
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 416 ms / 4,000 ms
コード長 10,312 bytes
コンパイル時間 1,536 ms
コンパイル使用メモリ 161,952 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-05-03 12:43:03
合計ジャッジ時間 5,138 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 1 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 3 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 3 ms
5,376 KB
testcase_28 AC 4 ms
5,376 KB
testcase_29 AC 411 ms
7,296 KB
testcase_30 AC 394 ms
6,940 KB
testcase_31 AC 331 ms
6,528 KB
testcase_32 AC 407 ms
7,296 KB
testcase_33 AC 132 ms
5,376 KB
testcase_34 AC 91 ms
5,376 KB
testcase_35 AC 416 ms
7,424 KB
testcase_36 AC 416 ms
7,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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]);
  }
}
int A[100000], B[100000], X[100000];
template<class T> struct lazySegtreeMin{
  T *addval, *data, *fixval;
  char *fixed;
  int N, logN;
  void malloc(int maxN){
    int i;
    for(i=1;i<maxN;i*=2){
      ;
    }
    data = (T*)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);
  }
  T& operator[](int i){
    return data[N+i];
  }
  void setN(int n, int zerofill = 1){
    int i;
    for(i=1,logN=0;i<n;i*=2,logN++){
      ;
    }
    N = i;
    if(zerofill){
      for(i=0;i<N;i++){
        data[N+i] = 0;
      }
    }
  }
  void build(void){
    int i;
    for(i=N-1;i;i--){
      data[i] = min(data[2*i],data[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){
    if(fixed[a]){
      if(sz > 1){
        fixed[a*2] = fixed[a*2+1] = 1;
        fixval[a*2] = fixval[a*2+1] = fixval[a];
        data[a*2] = data[a*2+1] = fixval[a];
      }
      else{
        data[a*2] = data[a*2+1] = fixval[a];
      }
      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];
        }
        data[a*2] += addval[a];
        data[a*2+1] += addval[a];
      }
      else{
        data[a*2] += addval[a];
        data[a*2+1] += addval[a];
      }
      addval[a] = 0;
      return;
    }
  }
  inline void push(int a){
    int aa, i;
    for(i=logN;i;i--){
      aa = a>>i;
      push_one(aa, 1<<(i-1));
    }
  }
  inline void build(int a){
    int sz=1;
    while(a > 1){
      a /= 2;
      sz *= 2;
      if(fixed[a]){
        data[a] = fixval[a];
      }
      else{
        data[a] = min(data[a*2], data[a*2+1]);
        if(addval[a] != 0){
          data[a] += addval[a];
        }
      }
    }
  }
  inline void change(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){
      data[a++] = val;
    }
    if(b%2){
      data[--b] = val;
    }
    a /= 2;
    b /= 2;
    while(a < b){
      sz *= 2;
      if(a%2){
        fixed[a]=1;
        fixval[a]=val;
        data[a++] = val;
      }
      if(b%2){
        fixed[--b]=1;
        fixval[b]=val;
        data[b] = val;
      }
      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){
      data[a++] += val;
    }
    if(b%2){
      data[--b] += val;
    }
    a /= 2;
    b /= 2;
    while(a < b){
      sz *= 2;
      if(a%2){
        if(fixed[a]){
          fixval[a] += val;
        }
        else{
          addval[a] += val;
        }
        data[a++] += val;
      }
      if(b%2){
        b--;
        if(fixed[b]){
          fixval[b] += val;
        }
        else{
          addval[b] += val;
        }
        data[b] += val;
      }
      a /= 2;
      b /= 2;
    }
    build(aa);
    build(bb-1);
  }
  inline T getMin(int a, int b){
    T res;
    int sz=1;
    a += N;
    b += N;
    push(a);
    push(b-1);
    res = 1000000000LL;
    while(a < b){
      if(a%2){
        res = min(res, data[a++]);
      }
      if(b%2){
        res = min(res, data[--b]);
      }
      a /= 2;
      b /= 2;
    }
    return res;
  }
}
;
int get_minind(lazySegtreeMin<long long> &y, int mm, long long h){
  int i, j, k;
  long long tmp;
  tmp = y.getMin(0, mm);
  if(tmp > -h){
    return -1;
  }
  i = 1;
  j = mm;
  while(i < j){
    k = (i+j) / 2;
    tmp = y.getMin(0,k);
    if(tmp <= -h){
      j = k;
    }
    else{
      i = k+1;
    }
  }
  return i-1;
}
int main(){
  int i, k;
  lazySegtreeMin<long long> t;
  long long H, N, W, res[2]={0LL, 0LL};
  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);
  t.setN(W);
  for(i=0;i<N;i++){
    t.add(X[i], X[i]+A[i], -B[i]);
    for(;;){
      k = get_minind(t, X[i]+A[i], H);
      if(k==-1){
        break;
      }
      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 20170428-1 [beta]

// --- original code ---
// template<class T>
// struct lazySegtreeMin{
//   int N, logN;
//   T *data;
//  
//   T *fixval; char *fixed;
//   T *addval;
//  
//   void malloc(int maxN){
//     int i;
//     for(i=1;i<maxN;i*=2);
//     
//     data = (T*)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);
//   }
//  
//   T& operator[](int i){
//     return data[N+i];
//   }
//  
//   void setN(int n, int zerofill = 1){
//     int i;
//     for(i=1,logN=0;i<n;i*=2,logN++);
//     N = i;
//     if(zerofill) rep(i,N) data[N+i] = 0;
//   }
//  
//   void build(void){
//     int i;
//     for(i=N-1;i;i--) data[i] = min(data[2*i],data[2*i+1]);
//     REP(i,1,N) fixed[i] = 0;
//     REP(i,1,N) addval[i] = 0;
//   }
//  
//   inline void push_one(int a, int sz){
//     if(fixed[a]){
//       if(sz > 1){
//         fixed[a*2] = fixed[a*2+1] = 1;
//         fixval[a*2] = fixval[a*2+1] = fixval[a];
//         data[a*2] = data[a*2+1] = fixval[a];
//       } else {
//         data[a*2] = data[a*2+1] = fixval[a];
//       }
//       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];
//         data[a*2] += addval[a];
//         data[a*2+1] += addval[a];
//       } else {
//         data[a*2] += addval[a];
//         data[a*2+1] += addval[a];
//       }
//       addval[a] = 0;
//       return;
//     }
//   }
//  
//   inline void push(int a){
//     int i, aa;
//     for(i=logN;i;i--){
//       aa = a>>i;
//       push_one(aa, 1<<(i-1));
//     }
//   }
//  
//   inline void build(int a){
//     int sz = 1;
//     while(a > 1){
//       a /= 2;
//       sz *= 2;
//       if(fixed[a]){
//         data[a] = fixval[a];
//       } else {
//         data[a] = min(data[a*2], data[a*2+1]);
//         if(addval[a] != 0) data[a] += addval[a];
//       }
//     }
//   }
//  
//   inline void change(int a, int b, T val){
//     int sz = 1, aa, bb;
//     if(a >= b) return;
//  
//     aa = (a += N);
//     bb = (b += N);
//     push(a); push(b-1);
//  
//     if(a%2) data[a++] = val;
//     if(b%2) data[--b] = val;
//     a /= 2;
//     b /= 2;
//  
//     while(a < b){
//       sz *= 2;
//       if(a%2) fixed[a]=1, fixval[a]=val, data[a++] = val;
//       if(b%2) fixed[--b]=1, fixval[b]=val, data[b] = val;
//       a /= 2;
//       b /= 2;
//     }
//  
//     build(aa);
//     build(bb-1);
//   }
//  
//   inline void add(int a, int b, T val){
//     int sz = 1, aa, bb;
//     if(a >= b) return;
//  
//     aa = (a += N);
//     bb = (b += N);
//     push(a); push(b-1);
//  
//     if(a%2) data[a++] += val;
//     if(b%2) data[--b] += val;
//     a /= 2;
//     b /= 2;
//  
//     while(a < b){
//       sz *= 2;
//       if(a%2){
//         if(fixed[a]) fixval[a] += val; else addval[a] += val;
//         data[a++] += val;
//       }
//       if(b%2){
//         b--;
//         if(fixed[b]) fixval[b] += val; else addval[b] += val;
//         data[b] += val;
//       }
//       a /= 2;
//       b /= 2;
//     }
//  
//     build(aa);
//     build(bb-1);
//   }
//  
//   inline T getMin(int a, int b){
//     T res;
//     int sz = 1;
//     
//     a += N;
//     b += N;
//     push(a); push(b-1);
//  
//     res = 1000000000LL;
//     while(a < b){
//       if(a%2) res = min(res, data[a++]);
//       if(b%2) res = min(res, data[--b]);
//       a /= 2;
//       b /= 2;
//     }
//     return res;
//   }
// };
//  
//  
//  
// int get_minind(lazySegtreeMin<ll> &y, int mm, ll h){
//   int i, j, k;
//   ll tmp;
//  
//   tmp = y.getMin(0, mm);
//   if(tmp > -h) return -1;
//  
//   i = 1;
//   j = mm;
//   while(i < j){
//     k = (i+j) / 2;
//     tmp = y.getMin(0,k);
//     if(tmp <= -h) j = k; else i = k+1;
//   }
//   return i-1;
// }
// 
// 
// int A[100000], B[100000], X[100000];
// {
//   int i,k;
//   ll N, W, H;
//   lazySegtreeMin<ll> t;
//   ll res[2] = {0LL, 0LL};
// 
//   rd(N,W,H,(A,B,X)(N));
//   X[0..N-1]--;
//   
//   t.malloc(W);
//   t.setN(W);
// 
//   rep(i,N){
//     t.add(X[i], X[i]+A[i], -B[i]);
//     for(;;){
//       k = get_minind(t, X[i]+A[i], H);
//       if(k==-1) break;
//       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");
// }
0