結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
コンテスト
ユーザー vjudge1
提出日時 2025-02-28 20:57:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 763 ms / 4,000 ms
コード長 2,157 bytes
コンパイル時間 3,262 ms
コンパイル使用メモリ 278,976 KB
実行使用メモリ 7,020 KB
最終ジャッジ日時 2025-02-28 20:58:06
合計ジャッジ時間 6,122 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define maxn 100005
using namespace std;
int n,m,p[maxn],lst,turn;
int block,blo[maxn],blol[50001],blor[50001];
ll tag[50001],ANS[2],h,a[maxn];
inline bool cmp(int i,int j){return a[i]+tag[blo[i]]<a[j]+tag[blo[j]];}
inline void modify(int l,int r,ll dt){
    if(blo[l]^blo[r]){
        for(int i=blo[l]+1;i<=blo[r]-1;++i){
            tag[i]+=dt;
            for(int j=blor[i];j>=blol[i];--j){
                if(a[p[j]]+tag[i]<h)break;
                ++ANS[turn];--blor[i];
            }
        }
        if(blol[blo[l]]<=blor[blo[l]]){
            for(int i=blol[blo[l]];i<=blor[blo[l]];++i)if(p[i]>=l)a[p[i]]+=dt;
            sort(p+blol[blo[l]],p+1+blor[blo[l]],cmp);
            for(int i=blor[blo[l]];i>=blol[blo[l]];--i){
                if(a[p[i]]+tag[blo[l]]>=h){++ANS[turn];--lst;--blor[blo[l]];}
                else break;
            }
        }
        if(blol[blo[r]]<=blor[blo[r]]){
            for(int i=blol[blo[r]];i<=blor[blo[r]];++i)if(p[i]<=r)a[p[i]]+=dt;
            sort(p+blol[blo[r]],p+1+blor[blo[r]],cmp);
            for(int i=blor[blo[r]];i>=blol[blo[r]];--i){
                if(a[p[i]]+tag[blo[r]]>=h){++ANS[turn];--lst;--blor[blo[r]];}
                else break;
            }
        }
    }
    else{
        for(int i=l;i<=r;++i)a[i]+=dt;
        if(blol[blo[l]]<=blor[blo[l]]){
            sort(p+blol[blo[l]],p+1+blor[blo[l]],cmp);
            for(int i=blor[blo[l]];i>=blol[blo[l]];--i){
                if(a[p[i]]+tag[blo[l]]>=h){++ANS[turn];--lst;--blor[blo[l]];}
                else break;
            }
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>m>>n>>h;block=200;lst=n;
    for(int i=1;i<=n;++i){
        blo[i]=(i-1)/block+1;
        if(!blol[blo[i]])blol[blo[i]]=i;
        blor[blo[i]]=i;p[i]=i;
    }
    while(m--){
        int a,x;ll b;
        cin>>a>>b>>x;
        modify(x,x+a-1,b);
        if(!lst)break;
        turn^=1;
    }
    if(ANS[0]==ANS[1])cout<<"DRAW\n";
    else if(ANS[0]>ANS[1])cout<<"A\n";
    else cout<<"B\n";
    // cout<<ANS[0]<<" "<<ANS[1];
	return 0;
}
0