记录编号	324671	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.766 s
提交时间	2016-10-18 16:47:57	内存使用	10.97 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define file(x) "qc."#x
using std::min;
using std::max;
typedef long long ll;
const int MAXN=2e5+10;
int n,m;
ll s,a[MAXN],cnt[MAXN],pre[MAXN],w[MAXN],v[MAXN],sl[MAXN],sr[MAXN],ans;
bool check(ll now){
	memset(pre,0,sizeof(pre));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++) {
		pre[i]=pre[i-1];
		cnt[i]=cnt[i-1];
		if(w[i]>=now){
			cnt[i]++;
			pre[i]+=v[i];
		}
	}
	ll y=0;
	for(int i=1;i<=m;i++) {
		y+=(pre[sr[i]]-pre[sl[i]-1])*(cnt[sr[i]]-cnt[sl[i]-1]);
	}
	ans=min(ans,llabs(y-s));
	return y<=s;
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	ll l=0,r=0,mid;
	scanf("%d%d%lld",&n,&m,&s);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&w[i],&v[i]),r=max(r,w[i]),ans+=v[i];
	ans*=n;
	r++;
	for(int i=1;i<=m;i++) scanf("%lld%lld",&sl[i],&sr[i]);
	while(l<r){//first pos <= s
		mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	ll nw=w[1];
	for(int i=1;i<=n;i++) if(w[i]>nw&&w[i]<l) nw=w[i];
	check(nw);
	printf("%lld",ans);
}