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

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,S,w[200005],v[200005],l[200005],r[200005],W,ma,s[200005],u[200005];
int pd(ll W)
{
	ll ans=0;
	memset(s,0,sizeof(s));
	memset(u,0,sizeof(u));
	for(int i=1;i<=n;i++)
	{
		s[i]=s[i-1];
		u[i]=u[i-1];
		if(w[i]>=W)s[i]+=v[i],u[i]++;
	}
	for(int i=1;i<=m;i++)
	{
		ans+=(s[r[i]]-s[l[i]-1])*(u[r[i]]-u[l[i]-1]);
	}
	if(ans==S)return 2;
	if(ans<S)return 1;
	if(ans>S)return 0;
}
void work()
{
	ll L=1,R=ma,ghb;
	while(L!=R)
	{
		ll mid=(L+R)>>1;
		int p=pd(mid);
		if(p==2)
		{
			ghb=S;
			break;
		}
		if(p)R=mid;
		else L=mid;
		if(L+1==R)
		{
			ll s1=0,s2=0;
			memset(s,0,sizeof(s));
			memset(u,0,sizeof(u));
			for(int i=1;i<=n;i++)
			{
				s[i]=s[i-1];
				u[i]=u[i-1];
				if(w[i]>=L)s[i]+=v[i],u[i]++;
			}
			for(int i=1;i<=m;i++)
			{
				s1+=(s[r[i]]-s[l[i]-1])*(u[r[i]]-u[l[i]-1]);
			}
			memset(s,0,sizeof(s));
			memset(u,0,sizeof(u));
			for(int i=1;i<=n;i++)
			{
				s[i]=s[i-1];
				u[i]=u[i-1];
				if(w[i]>=R)s[i]+=v[i],u[i]++;
			}
			for(int i=1;i<=m;i++)
			{
				s2+=(s[r[i]]-s[l[i]-1])*(u[r[i]]-u[l[i]-1]);
			}
			if(abs(s1-S)<abs(s2-S))
			{
				R=L;
				ghb=s1;
			}
			else 
			{
				L=R;
				ghb=s2;
			}
		}
	}
	cout<<abs(ghb-S);
}
int main()
{
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%lld%lld%lld",&n,&m,&S);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&w[i],&v[i]);
		ma=max(ma,w[i]);
	}
	for(int i=1;i<=m;i++)
	scanf("%lld%lld",&l[i],&r[i]);
	work();
	return 0;
}