結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
ユーザー LayCurse
提出日時 2017-04-30 01:02:30
言語 C++11
(gcc 13.3.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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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]);
}
}
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");
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0