結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
ユーザー CZS_AK_IOI2025
提出日時 2025-03-31 20:28:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,132 bytes
コンパイル時間 2,303 ms
コンパイル使用メモリ 197,084 KB
実行使用メモリ 7,328 KB
最終ジャッジ日時 2025-03-31 20:28:49
合計ジャッジ時間 5,030 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 5
other WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
#define ll 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>>n>>m>>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