记录编号	334603	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	1.198 s
提交时间	2016-11-01 11:17:53	内存使用	6.42 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>


using namespace std;


const int nmax=200086;


typedef long long ll;


int n,m;
ll S;


int tmpmax;


ll num[nmax]={0};
ll pre[nmax]={0};
int w[nmax]={0},v[nmax]={0};


class poi
{
public:
	int l,r;
	poi()
	{
		l=0;
		r=0;
	}
}Q[nmax];


void PreDo()
{
	scanf("%d%d%lld",&n,&m,&S);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&w[i],&v[i]);
		if(w[i]>tmpmax)
		{
			tmpmax=w[i];
		}
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&Q[i].l,&Q[i].r);
	}
}


ll Colculate(int tmpw)
{
	
	
	memset(num,0,sizeof(num));
	memset(pre,0,sizeof(pre));
	
	for (int i=1;i<=n;i++)
	{
		pre[i]=pre[i-1];
		num[i]=num[i-1];
		if (w[i]>=tmpw)
		{
			pre[i]+=v[i];
			num[i]++;
		}
	}
	
	ll y=0;
	
	
	for (int i=1;i<=m;i++)
	{
		y+=1ll*(num[Q[i].r]-num[Q[i].l-1])*(pre[Q[i].r]-pre[Q[i].l-1]);
	}
	
	
	return y;
}


bool Check(int tmpx)
{
	if(Colculate(tmpx)<S)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}


ll BiSearch(ll lft,ll rgt)
{
	while(lft+1<rgt)
	{
		int mid=(lft+rgt)>>1;
		if(Check(mid))
		{
			rgt=mid;
		}
		else
		{
			lft=mid;
		}
	}
	
	
	ll dertal=abs(S-Colculate(lft));
	ll dertar=abs(S-Colculate(rgt));
	
	
	if(dertal<dertar)
	{
		printf("%lld\n",dertal);
	}
	else
	{
		printf("%lld\n",dertar);
	}
}



int main()
{
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);
	PreDo();
	BiSearch(0,tmpmax);
	return 0;
}