记录编号	465558	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.550 s
提交时间	2017-10-27 11:25:32	内存使用	7.92 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010;
int n,m,ll[maxn],rr[maxn];
long long w[maxn],v[maxn],c[maxn],f[maxn];
long long s,l,r,tmp,ans=1e15;
long long Abs(long long x){return (x>0)?x:-x;}
void check(int x){
	memset(c,0,sizeof(c));
	memset(f,0,sizeof(f));
	for(int i=1;i<=n+1;i++)c[i]=c[i-1]+(w[i-1]>=x),f[i]=f[i-1]+((w[i-1]>=x)?v[i-1]:0);
	tmp=0;
	//for(int i=1;i<=n;i++)printf("%lld %lld\n",c[i],f[i]);
	for(int i=1;i<=m;i++)tmp+=(c[rr[i]+1]-c[ll[i]])*(f[rr[i]+1]-f[ll[i]]);
	if(Abs(tmp-s)<ans)ans=Abs(tmp-s);
}
int main(){
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);
	scanf("%d%d%lld",&n,&m,&s);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&w[i],&v[i]),r=max(r,w[i]);
	for(int i=1;i<=m;i++)scanf("%d%d",&ll[i],&rr[i]);
	while(l<=r){
		long long mid=(l+r)>>1;
		check(mid);
		if(tmp<s)r=mid-1;
		if(tmp>s)l=mid+1;
		if(tmp==s)break;
	}
	printf("%lld\n",ans);
	return 0;
}