记录编号	386638	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	FFF团	是否通过	通过
代码语言	C++	运行时间	1.402 s
提交时间	2017-03-24 20:35:52	内存使用	9.47 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long int n,m,s,ans=9000000000000000000,ld,ud,mid;
long long int w[200000+10],v[200000+10],sum[200000+10],sumv[200000+10],l[200000+10],r[200000+10];
bool C(int x){
	int p;
	long long int y=0,t;
	for(int i=1;i<=n;i++)
	    if(w[i]>=x){
		    sum[i]=sum[i-1]+1;
		    sumv[i]=sumv[i-1]+v[i];
	    }
	    else{
		    sum[i]=sum[i-1];
		    sumv[i]=sumv[i-1];
	    }
	for(int i=1;i<=m;i++){
		y=y+((sum[r[i]]-sum[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]));
	}
	if(s>y){
		p=0;
		t=s-y;
	}
	else{
		p=1;
		t=y-s;
	}
	ans=min(ans,t);
	return p;
}
int main(){
	//ios::sync_with_stdio(false);
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
		ld=min(ld,w[i]);
		ud=max(ud,w[i]);
	}
	for(int i=1;i<=m;i++) cin>>l[i]>>r[i];
	while(ld<=ud){
		mid=(ld+ud)/2;
		if(C(mid)) ld=mid+1;
		else ud=mid-1;
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}