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

#include<iostream>
#include<cstdio>
using namespace std;
long long  n,m,w[200001],l[200001],r[200001],v[200001],sum[200001],sumv[200001],s,min1=123456789123456789;
bool check(int x)
{
	int i;
	long long y=0,p;
	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+=(sum[r[i]]-sum[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
	if(s>y)
	{
	  p=s-y;
	  i=0;
	}
	else
	{
	  p=y-s;
	  i=1;
	}
	if(p<min1)min1=p;
	return i;
}
int main()
{
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);
	long long i,j,l1=1000001,r1=-1,mid;
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	{
	  cin>>w[i]>>v[i];
	  if(w[i]<l1)l1=w[i];
	  if(w[i]>r1)r1=w[i];
	}
	for(int i=1;i<=m;i++)
	  cin>>l[i]>>r[i];
	while(l1<=r1)
	{
	  mid=(l1+r1)/2;
	  if(check(mid))
	  	l1=mid+1;
	  else r1=mid-1;
	}
	cout<<min1;
}