CodeForcse 1305H Kuroni the Private Tutor

https://codeforces.com/contest/1305/problem/H

(m) 个同学参加了一场考试,有 (n) 道题,每道题的分数都是 (1) .你碰巧的瞥了一眼最终成绩单,得知了一些信息

第 (i) 道题至少有 (L_i) 个同学做出来了,至多有 (R_i) 个同学做出来
第 (p_i) 名的分数为 (s_i) , (i in [1,q])
所有同学的总分为 (T)

其中排名的顺序为第一名得分最高,最后一名得分最低,分数相同的顺序任意.

问最多有多少名同学分数和第一名相同,在满足和第一名相同成绩的人数最大化的同时,第一名的分数最大为多少.

特别的,如果不存在满足以上限制的成绩单,输出"-1 -1"

(1 le n,m le 10^5) , (0 le q le m)

(0 le l_i le r_i le m)

(1 le p_i le m, 0 le s_i le n) ,满足 (p_i) 互不相同,且对于任意 (i,j in [1,q]) ,若 (p_i le p_j) ,则 (s_i ge s_j)

Tutorial

考虑假设我们已经决定了每位同学的分数 (b_1 le b_2 le cdots, le b_m, sum b_i = T) ,想要判断是否存在给每个同学分配它做对的题目集合,使得满足 (L_i,R_i) 限制的方案.

发现这个可以建立上下界网络流模型,设立源点和汇点,还有 (n) 个点表示题目, (m) 个点表示同学.源点向第 (i) 个题目的点连接上界为 (L_i) 下界为 (R_i) 的边,第 (i) 个同学向汇点连接上界,下界均为 (b_i) 的边.每对题目和同学之间连接上界为 (1) ,下界为 (0) 的边.

那么我们需要满足两个条件

存在可行流
最大流为 (T)

可以利用最小割的模型来思考,可以枚举最小割的形式,得到这样的式子

[min{ sumL_j+B_i+(n-j)(m-i) } ge sL \ min{ sumR_j+B_i+(n-j)(m-i) } ge T ]

其中 (sumL_j) 表示 (L) 中前 (i) 小的数的和, (sumR_i) 表示 (R) 中前 (i) 小的数的和, (B_i = sum_{j=1}^i b_j) . (sL) 表示所有 (L) 的和.

这可以用斜率优化做到 (O(n+m)) 判断.

显然,和第一名相同的同学数是可以二分的.

而从最后的式子的形式可以看出,若 (a) majorize (b) ,那么 (a) 作为 (B) 会比 (b) 作为 (B) 更优秀,也就是说让排名小的同学分数尽量大是更优的,所以第一名的分数也是可以二分的.

在二分第一名的分数的时候,需要分别考虑一下两种情况

被 (p_i,s_i,T) 的限制而判非法
被 (L_i,R_i) 的限制而判非法

Code

https://codeforces.com/contest/1305/submission/72366397

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define invalid0(a,b,c) (A[b]-A[a])*(c-b)>=(A[c]-A[b])*(b-a)
#define invalid1(a,b,c) (ll)(a)*(c-b)<=(A[c]-A[b])
#define fi first
#define se second
using namespace std;
inline char nc()
{
	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
	x=0; int f=1,ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x*=f; 
}
template<class T> inline bool Cmin(T &x,T y) {return x>y?x=y,1:0;}
typedef long long ll;
typedef pair<int,int> pii;
const ll INF=1e18;
const int maxn=1e5+50;
int n,m,q; ll T;
int mx;
int re;
int a[maxn];
int b[maxn];
int tmp[maxn];
ll sL;
ll sum;
ll B[maxn]; 
ll L[maxn];
ll R[maxn];
bool check0(ll rest)
{
	vector<pii> rec;
	int now=1;
	for(int i=1;i<=m;++i)
	{
		if(a[i]!=-1)
		{
			if(now<i) rec.push_back(make_pair(now,i-1));
			now=i+1;
		}
	}
	for(int i=0;i<rec.size()&&rest;++i)
	{
		int l=rec[i].fi,r=rec[i].se;
		ll d=(ll)(r-l+1)*(B[r+1]-B[r]);
		if(rest>=d) 
		{
			rest-=d;
			for(int j=l;j<=r;++j) B[j]=B[r+1];
		}
		else
		{
			int x=rest/(r-l+1),y=rest-(ll)x*(r-l+1);
			for(int j=l;j<=r;++j)
			{
				B[j]+=x;
				if(r-j+1<=y) ++B[j];
			}
			rest=0;
		}
	}
	return rest==0;
}
ll cal(ll *A)
{
	static int sta[maxn]; int top=0;
	for(int i=0;i<=n;++i)
	{
		while(top>1&&invalid0(sta[top-1],sta[top],i)) --top;
		sta[++top]=i;
	}
	ll mn=INF;
	for(int i=0;i<=m;++i)
	{
		while(top>1&&invalid1(m-i,sta[top-1],sta[top])) --top;
		int x=sta[top];
		Cmin(mn,A[x]+B[i]+(ll)(n-x)*(m-i));
	}
	return mn;
}
bool check1()
{
//	for(int i=1;i<=n;++i) debug("%lld ",L[i]); debug("
");
//	for(int i=1;i<=n;++i) debug("%lld ",R[i]); debug("
");
//	for(int i=1;i<=m;++i) debug("%lld ",B[i]); debug("
");
	for(int i=1;i<=m;++i) B[i]+=B[i-1];
	assert(B[m]==T);
	return cal(L)>=sL&&cal(R)>=T;
} 
bool sol(int len)
{
	int rec=-1;
	for(int i=m-len+1;i<=m;++i) if(a[i]!=-1)
	{
		if(rec!=-1&&rec!=a[i]) return 0;
		rec=a[i];
	}
	int l,r; bool ok=0;
	if(rec!=-1) l=r=rec;
	else  l=mx,r=min((ll)n,(T-sum)/len+mx);
//	l=r=8;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		for(int i=1;i<=m;++i) B[i]=b[i];
		ll rest=T-sum;
		for(int i=m-len+1;i<=m;++i)
		{
			rest-=mid-B[i]; B[i]=mid;
			tmp[i]=a[i],a[i]=mid;
		}
//		debug("%lld
",rest);
//		for(int i=1;i<=m;++i) debug("%lld ",B[i]); debug("
");
		if(rest<0)
		{
			r=mid-1;
		}
		else if(!check0(rest)) 
		{
			l=mid+1;
		}
		else
		{
			if(check1()) ok=1,re=mid,l=mid+1;
			else r=mid-1;
		}
		for(int i=m-len+1;i<=m;++i)
		{
			a[i]=tmp[i];
		}
	}
	return ok;
}
int main()
{
	read(n),read(m);
	for(int i=1;i<=n;++i)
	{
		read(L[i]),read(R[i]);
	}
	read(q);
	memset(a,-1,sizeof(a));
	for(int i=1;i<=q;++i)
	{
		int p,s; read(p),read(s);
		a[p]=s;
	}
	read(T);
	sort(L+1,L+n+1);
	sort(R+1,R+n+1);
	for(int i=1;i<=n;++i)
	{
		L[i]+=L[i-1];
		R[i]+=R[i-1];
	}
	sL=L[n];
	reverse(a+1,a+m+1);
	for(int i=1;i<=m;++i)
	{
		if(a[i]!=-1) mx=a[i];
		b[i]=mx;
		sum+=mx;
	}
	if(sum>T)
	{
		puts("-1 -1");
		return 0;
	} 
	int l=1,r=m,an=-1; re=-1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(sol(mid)) an=mid,l=mid+1;
		else r=mid-1;
	}	
//	cerr<<sol(7)<<endl;
	printf("%d %d
",an,re);
	return 0;
}