记录编号	470513	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	爆零自动机	是否通过	通过
代码语言	C++	运行时间	0.485 s
提交时间	2017-11-04 20:32:57	内存使用	9.47 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

typedef long long ll;

const int maxn=200000+3;

ll n,m;
ll w[maxn],v[maxn];
ll l[maxn],r[maxn];
ll s,ans=0x4000000000000000;
ll sum[maxn],cnt[maxn];

ll getsum(ll wt);
ll y(ll w);

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",&l[i],&r[i]);
	
	ll left=0,right=200000+1;
	while(left<=right)
	{
		ll mid=(left+right)/2;
		ll t=y(mid);
		ans=min(ans,abs(t-s));
		if(t<s)
		{
			right=mid-1;
		}
		else
		{
			left=mid+1;
		}
	}
	
	printf("%lld\n",ans);
	return 0;
}
ll getsum(ll wt)
{
	sum[0]=0; 
	for(int i=1; i<=n; i++)
	{
		sum[i]=sum[i-1];
		cnt[i]=cnt[i-1];
		if(w[i]>=wt)
		{
			sum[i]+=v[i];
			cnt[i]++;
		}
	}
}
ll y(ll w)
{
	ll y=0;
	getsum(w);
	for(int i=1; i<=m; i++)
	{
		y+=(sum[r[i]]-sum[l[i]-1])*(cnt[r[i]]-cnt[l[i]-1]);
	}
	return y;
}