记录编号	451574	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.521 s
提交时间	2017-09-17 21:44:16	内存使用	6.61 MiB

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
LL n,m,s,ans=1e13,w[200010],v[200010],l=1,r=1e7;
LL sum[200010],cnt[200010],ql[200010],qr[200010],temp;
LL check(LL x)
{
	temp=0;
	memset(sum,0,sizeof(sum));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++)
	{
		if(w[i]>=x)
		{
			sum[i]=sum[i-1]+v[i];
			cnt[i]=cnt[i-1]+1;
		}
		else
		{
			sum[i]=sum[i-1];
			cnt[i]=cnt[i-1];
		}
	}
	for(int i=1;i<=m;i++)temp+=(cnt[qr[i]]-cnt[ql[i]-1])*(sum[qr[i]]-sum[ql[i]-1]);
	return temp;
}
int Main()
{
	freopen("qc.in","r",stdin);freopen("qc.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&s);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&w[i],&v[i]);
	for(int i=1;i<=m;i++)scanf("%lld%lld",&ql[i],&qr[i]);
	while(l!=r)
	{
		if(l>r)break;
		LL mid=l+((r-l)>>1);
		LL tmp=check(mid);
		if(tmp>s)
		{
			l=mid+1;
			if(tmp-s<ans)ans=tmp-s;
		}
		else
		{
			r=mid;
			if(s-tmp<ans)ans=s-tmp;
		}
	}
	printf("%lld\n",ans);
	return 0;
}
int main(){;}
int syy=Main();