提出 #75916184

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define VI vector<int>
#define VII vector<pii>
#define VL vector<ll>
#define VLL vector<pll>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)

#define LOCAL true

using namespace std;
bool st;
const bool MUL=true;
const int MAXN=1e7+10,N=3e5+10;
struct nd{int ls,rs,c;ll s;}tr[MAXN];
int n_c,rt;
ll n,m,k,a[N],ans[N];

void clr(){rep(i,0,n_c)tr[i]={0,0,0,0};n_c=rt=0;return;}
void upd(int&p,int l,int r,int v,int d){
	if(!p)p=++n_c;
	tr[p].c+=d,tr[p].s+=1ll*v*d;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(v<=mid)upd(tr[p].ls,l,mid,v,d);
	else upd(tr[p].rs,mid+1,r,v,d);
	return;
}

int get_mn(int p,int l,int r){
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(tr[tr[p].ls].c>0)return get_mn(tr[p].ls,l,mid);
	return get_mn(tr[p].rs,mid+1,r);
}

int pop_mn(int p,int l,int r){
	tr[p].c--;
	if(l==r){tr[p].s-=l;return l;}
	int mid=(l+r)>>1,res;
	if(tr[tr[p].ls].c>0)res=pop_mn(tr[p].ls,l,mid);
	else res=pop_mn(tr[p].rs,mid+1,r);
	tr[p].s-=res;
	return res;
}

void qry(int p,int l,int r,ll rem,ll&km,ll&sm){
	if(!p||rem<=0)return;
	if(tr[p].s<=rem){km+=tr[p].c,sm+=tr[p].s;return;}
	if(l==r){
		ll tk=min((ll)tr[p].c,rem/l);
		km+=tk,sm+=tk*l;
		return;
	}
	int mid=(l+r)>>1;
	if(tr[tr[p].ls].s<=rem){
		ll lc=tr[tr[p].ls].c,ls=tr[tr[p].ls].s;
		km+=lc,sm+=ls;
		qry(tr[p].rs,mid+1,r,rem-ls,km,sm);
	}else qry(tr[p].ls,l,mid,rem,km,sm);
	return;
}

void solve(){
	cin>>n>>m>>k;
	rep(i,1,n)cin>>a[i];
	ll f0=0,sd=0,cd=0,vp=0;
	rep(i,1,n){
		ll rem=max(0ll,k-f0),um=0;
		if(sd<=rem)um=k+vp-f0+cd*m-sd;
		else{
			ll km=0,sm=0;
			qry(rt,1,m,rem,km,sm);
			um=k+vp-f0+km*m-sm;
		}
		ll ta=um>=m-a[i]?0:a[i];
		ans[i]=ta;
		ll vi=(ta-a[i])%m;
		if(vi<0)vi+=m;
		ll du=(vi-vp)%m;
		if(du<0)du+=m;
		if(du){
			if(vi<vp)upd(rt,1,m,du,1),sd+=du,cd++;
			else{
				ll md=m;
				if(cd>0)md=get_mn(rt,1,m);
				if(du<=md)f0+=du;
				else{
					if(cd>0)pop_mn(rt,1,m),sd-=md,cd--;
					f0+=md,upd(rt,1,m,du,1),sd+=du,cd++;
				}
			}
		}
		vp=vi;
	}
	rep(i,1,n)cout<<ans[i]<<" \n"[i==n];
	return; 
}

bool ed;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tc=1;if(MUL){cin>>tc;}while(tc--)clr(),solve();
// 	cerr<<"time:"<<clock()<<"ms.\n";
// 	cerr<<fixed<<setprecision(4)<<"memory:"<<(1.0*(&st-&ed)/1048576.0)<<"MB.\n";
	return 0;
}

提出情報

ジャッジ結果