记录编号	385786	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	Emine	是否通过	通过
代码语言	C++	运行时间	1.362 s
提交时间	2017-03-22 15:45:12	内存使用	9.47 MiB

#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
const long long maxn=200100;
long long n,m,S,maxw;
long long w[maxn],v[maxn],l[maxn],r[maxn],sum[maxn],cnt[maxn];
long long ef(long long W)
{
	for(long long i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]; 
		cnt[i]=cnt[i-1];
		if(w[i]>=W)
		{
		    sum[i]+=v[i];
			cnt[i]++;
		}
	}
	long long ans=0;
	for(long long i=1;i<=m;i++) 
	  ans+=(cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
	return ans;
}
int main()
{
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);
	cin>>n>>m>>S;
	for(long long i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i]; 
		maxw=max(maxw,w[i]);
	}
	for(long long i=1;i<=m;i++) 
	{
		cin>>l[i]>>r[i];
	}  
	long long l=0,r=maxw+1,mid;
	while(l<r-1)
	{
		mid=l+(r-l)/2;
		if(ef(mid)>S) l=mid;
		else r=mid;
	}
	cout<<min(abs(ef(l)-S),abs(ef(r)-S));
	return 0;
}