记录编号	136625	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	0.220 s
提交时间	2014-11-03 13:33:30	内存使用	15.16 MiB

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
int s[200001],t[200001],w[200001],v[200001];
long long V[200001],sum[200001];
char *ptr=new char[10000000];
inline void in(int &x){
    while(*ptr<'0'||*ptr>'9')++ptr;
    x=0;
    while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
inline void in(long long &x){
    while(*ptr<'0'||*ptr>'9')++ptr;
    x=0;
    while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
int main(){
    freopen("qc.in","r",stdin),freopen("qc.out","w",stdout);
    fread(ptr,1,10000000,stdin);
    int n,M,i,l,r=0,m;
    long long S,ansl=0,ansr=0,ansm;
    in(n),in(M),in(S);
    for(i=1,++n;i<n;++i)
        in(w[i]),in(v[i]),r=max(r,w[i]);
    for(i=1;i<n;++i)
        V[i]=V[i-1]+v[i];
    for(i=0;i<M;++i){
        in(s[i]),in(t[i]);
        --s[i];
        ansl+=(t[i]-s[i])*(V[t[i]]-V[s[i]]);
    }
    l=1,++r;
    while(r-l>1){
        m=(l+r)>>1,ansm=0;
        for(i=1;i<n;++i)
            V[i]=V[i-1]+(w[i]>=m)*v[i];
        for(i=1;i<n;++i)
            sum[i]=sum[i-1]+(w[i]>=m);
        for(i=0;i<M;++i)
            ansm+=(V[t[i]]-V[s[i]])*(sum[t[i]]-sum[s[i]]);
        if(ansl>=S&&S>=ansm)
            r=m,ansr=ansm;
        if(ansm>=S&&S>=ansr)
            l=m,ansl=ansm;
    }
    printf("%lld",min(abs(S-ansl),abs(S-ansr)));
    return 0;
}