436F - Banners - CodeForces Solution

#include<cstdio>
#include<algorithm>
const int D=200,N=1e5+2;
int c,i,j,k,t,n,m,w,f[502],r[502],h[502];
long long s,ans,x[N];
struct Z{
	int a,b;
	bool operator<(const Z&a)const{
		return b<a.b;
	}
}a[N];
int B(int i)
{
	int j,k,L=(i-1)*D,R=std::min(m,i*D);
	for(k=L+1,j=L;j++<R;x[k]<x[j]?k=j:0)x[j]+=1ll*j*f[i];
	for(f[i]=0,h[i]=N,r[i]=j=k;j++<R;h[i]=std::min(1ll*h[i],(x[k]-x[j])/(j-k)));
}
int main()
{
	for(scanf("%d%d",&n,&w);i++<n;m=m<a[i].a?a[i].a:m)
		scanf("%d%d",&a[i].a,&a[i].b);
	std::sort(a+1,a+n+1);
	for(i=1;c<=a[n].b+1;++c)
	{
		for(;i<=n&&a[i].b<c;++i,ans=k=0,B(t))
		{
			for(j=0;++j*D<=a[i].a;++f[j],!h[j]--?B(j):0);
			for(t=j,j=(j-1)*D;j++<a[i].a;x[j]+=j);
		}
		if(!k)for(j=0;j++*D<m;ans<s?ans=s,k=r[j]:0)s=x[r[j]]+1ll*f[j]*r[j];
		printf("%lld %d\n",ans+1ll*c*w*(n-i+1),k);
	}
}/*1692657872.6105003*/