记录编号	444231	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.556 s
提交时间	2017-09-02 14:27:50	内存使用	6.42 MiB

#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

const int MAXN=200010;

int n;
int m;
int w[MAXN];
int l[MAXN];
int r[MAXN];
long long S;
int cnt[MAXN];
long long v[MAXN];
long long sum[MAXN];
long long ans=LLONG_MAX;

void Initialize();
long long Calc(int);

int main(){
	Initialize();
	int l=1,r=1e6;
	while(l<r){
		int mid=(l+r)>>1;
		long long x=Calc(mid);
		ans=std::min(ans,llabs(S-x));
		// printf("l=%d r=%d x=%lld ans=%lld\n",l,r,x,ans);
		if(x>S)
			l=mid+1;
		else
			r=mid;
	}
	printf("%lld\n",ans);
	return 0;
}

inline long long Calc(int W){
	for(int i=1;i<=n;i++){
		sum[i]=w[i]>=W?v[i]+sum[i-1]:sum[i-1];
		cnt[i]=w[i]>=W?cnt[i-1]+1:cnt[i-1];
	}
	long long ans=0;
	for(int i=1;i<=m;i++){
		ans+=(cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
	}
	return ans;
}

void Initialize(){
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);
	scanf("%d%d%lld",&n,&m,&S);
	for(int i=1;i<=n;i++){
		scanf("%d%lld",w+i,v+i);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",l+i,r+i);
	}
}