ABC 314 G

SFlyer / 2023-08-13 / 原文

简单题，但是我赛时没写完，少了一个 \(5\) 分钟。

link

程序有点丑，就不放 link 了，去掉注释在这。

code

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;

const int N = 6e5+5;

ll n,m,h,a[N],b[N],A[N],L[N],lst[N];
ll cur[N];
ll bit[N],bit2[N];
vector<ll> g[N];
map<ll,ll> mp;
map<ll,ll> c;
int Lst[N];

void M(ll x,ll y){
	while (x<=n*2){
		bit[x]+=y;
		x+=x&-x;
	}
}

void M2(ll x,ll y){
	while (x<=n*2){
		bit2[x]+=y;
		x+=x&-x;
	}
}

ll S(ll x){
	ll res=0;
	while (x>0){
		res+=bit[x];
		x-=x&-x;
	}
	return res;
}

ll Q(ll l,ll r){
	return S(r)-S(l-1);
}

ll S2(ll x){
	ll res=0;
	while (x>0){
		res+=bit2[x];
		x-=x&-x;
	}
	return res;
}

ll Q2(ll l,ll r){
	return S2(r)-S2(l-1);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>m>>h;
	multiset<ll> st;
	for (int i=1; i<=n; i++){
		cin>>a[i]>>b[i];
		st.insert(a[i]+cur[b[i]]);
		ll t=a[i];
		a[i]=a[i]+cur[b[i]];
		A[i]=a[i];
		lst[i]=cur[b[i]];
		L[i]=lst[i];
		cur[b[i]]+=t;
	}
	int cnt=0,cnt2=0;
	for (auto u : st){
		if (!mp.count(u)){
			mp[u]=++cnt;
		}
		g[mp[u]].push_back(++cnt2);
	}
	for (int i=1; i<=n; i++){
		ll t=mp[a[i]];
		a[i]=g[t][c[t]++];
		t=mp[lst[i]];
		if (Lst[b[i]]!=0) lst[i]=a[Lst[b[i]]];
		Lst[b[i]]=i;
	}
	int pos=0;
	for (int i=0; i<=m; i++){
		int hv=i;
		while (pos<=n){
			pos++;
			if (pos==n+1){
				break;
			}
			if (lst[pos]){
				M(lst[pos],-1);
			}
			M(a[pos],1);
			if (lst[pos]){
				M2(lst[pos],-L[pos]);
			}
			M2(a[pos],A[pos]);
			int l=-1,r=n*2+1;
			while (l+1<r){
				int mid=l+r>>1;
				if (Q(mid,n*2)>hv){
					l=mid;
				}
				else{
					r=mid;
				}
			}
			ll tmp=Q2(1,r-1);
			if (tmp>=h){
				if (lst[pos]){
					M(lst[pos],1);
				}
				M(a[pos],-1);
				if (lst[pos]){
					M2(lst[pos],L[pos]);
				}
				M2(a[pos],-A[pos]);
				break;
			}
		}
		pos--;
		cout<<pos<<" ";
	}
	cout<<endl;
	return 0;
}

// don't waste time!!!

我的做法和 Editorial 不一样，是 \(O(m\log^2 n)\) 的，更差，但是 \(\sim 1000\) ms 可过。

首先考虑离散化。