luoguP1314 聪明的质监员 题解(NOIP2011)

P1314 聪明的质监员 题目

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<iomanip>

#include<ctime>

#include<queue>

#include<stack>

#define rg register

#define lst long long

#define N 200050

#define Inf 2147483647

using namespace std;

int n,m,mx=-,mn=Inf;

lst res,s,ss;

lst ans=;

int w[N],v[N],l[N],r[N];

lst tot[N],num[N];

inline lst read()

{

    rg lst s=,m=;rg char ch=getchar();

    while(ch!='-'&&(ch<''||ch>''))ch=getchar();

    if(ch=='-')m=-,ch=getchar();

    while(ch>=''&&ch<='')s=(s<<)+(s<<)+ch-'',ch=getchar();

    return s*m;

}

inline lst a_b_s(rg lst t){return t>=?t:-t;}

inline bool check(rg int lim)

{

    res=,ss=;

    memset(tot,,sizeof(tot));

    memset(num,,sizeof(num));

    for(rg int i=;i<=n;++i)

    {

        num[i]=num[i-],tot[i]=tot[i-];

        if(w[i]>=lim)num[i]++,tot[i]+=v[i];

    }

    for(rg int i=;i<=m;++i)

        ss+=(num[r[i]]-num[l[i]-])*(tot[r[i]]-tot[l[i]-]);

    res=a_b_s(ss-s);

    if(ss>s)return ;

    else return ;

}

int main()

{

    n=read(),m=read(),s=read();

    for(rg int i=;i<=n;++i)

    {

        w[i]=read(),v[i]=read();

        mx=max(mx,w[i]),mn=min(mn,w[i]);

    }

    for(rg int i=;i<=m;++i)

        l[i]=read(),r[i]=read();

    rg int le=mn-,ri=mx+;

    while(le<=ri)

    {

        rg int mid=(le+ri)>>;

        if(check(mid))le=mid+;

        else ri=mid-;

        ans=min(ans,res);

    }

    cout<<ans<<endl;

    return ;

}