记录编号	385596	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	TARDIS	是否通过	通过
代码语言	C++	运行时间	0.374 s
提交时间	2017-03-21 21:02:24	内存使用	9.41 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<deque>
#define itn int
#define xlm mylove
#define maxn 200100
using namespace std;
long long n,a[maxn],m;long long s,answ1,answ2;
long long w[maxn],v[maxn],wsum[maxn],vsum[maxn];
long long l[maxn],r[maxn];
long long Min=10000000,Max=-1;
long long v1[maxn],v2[maxn],V[maxn],V1[maxn];
inline void in(){
	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%d",&w[i],&v[i]);
		Min=min(Min,w[i]);
		Max=max(Max,w[i]);
		wsum[i]=wsum[i-1]+w[i];
		vsum[i]=vsum[i-1]+v[i];
	}
	for (int i=1;i<=m;i++){
		scanf("%d%d",&l[i],&r[i]);
	}
	answ1=answ2=s;
}
inline void out(){
	printf("%lld",min(answ1,answ2));
	fclose(stdin);
	fclose(stdout);
}
inline long long cal(int x){
	long long ans=0;
	for (int i=1;i<=n;i++){
		if (w[i]>x){
			v1[i]=v1[i-1]+v[i];
			v2[i]=v2[i-1]+1;
		}
		else {
			v1[i]=v1[i-1];
			v2[i]=v2[i-1];
		}
		}
	for (int i=1;i<=m;i++){
		ans+=(v2[r[i]]-v2[l[i]-1])*(v1[r[i]]-v1[l[i]-1]);
	}
	return ans;
}
inline void work(){
	int left=Min,right=Max;
	while (left<=right){
		int mid=(left+right)>>1;
		long long now=cal(mid);
		if (now<s) {
			right=mid-1;
		}
		else {
			//answ1=min(answ1,abs(now-s));
			left=mid+1;
		}
	}
	//printf("%d %d\n",left,right);
	answ1=abs(cal(left)-s);answ2=abs(cal(right)-s);
}
int Main(){
	in();
	memset(v1,0,sizeof(v1));
	memset(v2,0,sizeof(v2));
	work();
	out();
	return 0;
}
int main(){;}
int xlm=Main();