记录编号	467201	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	631.[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	1.738 s
提交时间	2017-10-30 10:13:16	内存使用	81.95 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define ll long long 
using namespace std;
const int maxn=2e5+10;
ll s;
int n,m,val[maxn],cl[maxn],cr[maxn],l,r;
struct dd{
	int v,id;
	inline bool operator < (const dd & a)const {
		return v<a.v;
	}
}data[maxn];
int rk[maxn];
int stot;
ll sum[maxn*20];
int cnt[maxn*20];
int ls[maxn*20],rs[maxn*20],gen[maxn],sz;
inline void change(int shang,int &xin,int l,int r,int nl,int nr,int v){
	xin=++sz;
	if(l>=nl&&r<=nr){
		sum[xin]=sum[shang]+(ll)v;
		cnt[xin]=cnt[shang]+1;
		return;
	}
	ls[xin]=ls[shang];rs[xin]=rs[shang];
	int m=(l+r)>>1;
	if(m>=nl)change(ls[shang],ls[xin],l,m,nl,nr,v);
	if(m<nr)change(rs[shang],rs[xin],m+1,r,nl,nr,v);
	sum[xin]=sum[ls[xin]]+sum[rs[xin]];
	cnt[xin]=cnt[ls[xin]]+cnt[rs[xin]];
}
struct out{
	int cnt;ll sum;
	out(){cnt=0;sum=0;}
	inline out operator + (const out & a)const {
		out c;
		c.cnt=cnt+a.cnt;
		c.sum=sum+a.sum;
		return c;
	}
};
inline out find(int shang,int xin,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr){
		out re;
		re.cnt=cnt[xin]-cnt[shang];
		re.sum=sum[xin]-sum[shang];
		return re;
	}
	int m=(l+r)>>1;
	out ans;
	if(m>=nl)ans=ans+find(ls[shang],ls[xin],l,m,nl,nr);
	if(m<nr)ans=ans+find(rs[shang],rs[xin],m+1,r,nl,nr);
	return ans;
}
inline ll cal(int g){
	ll ans=0;
	for(int i=1;i<=m;i++){
		out calans=find(gen[cl[i]-1],gen[cr[i]],1,stot,g,stot);
		ans+=(ll)calans.cnt*calans.sum;
	}
	return ans;
}
inline void work(){
	ll ans=0x3f3f3f3f3f3f3f3fll;
	for(int i=1;i<=n;i++){
		change(gen[i-1],gen[i],1,stot,rk[i],rk[i],val[i]);
	}
	l=0;r=stot;
	while(l<=r){
		int m=(l+r)>>1;
		ll calans=cal(m);
		if(calans>s)l=m+1;
		else r=m-1;
		ans=min(ans,abs(calans-s));
	}
	printf("%lld\n",ans);
}
int main(){
	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",&data[i].v,&val[i]);
		data[i].id=i;
	}
	for(int i=1;i<=m;i++)scanf("%d%d",&cl[i],&cr[i]);
	sort(data+1,data+n+1);
	for(int i=1;i<=n;i++){
		if(data[i].v!=data[i-1].v)stot++;
		rk[data[i].id]=stot;
	}
	work();
	return 0;
}