codevs 1138 聪明的质监员

二分+前缀和。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 200500
#define inf 0x7f7f7f7f7f7f7f7fll
using namespace std;
long long n,m,s,w[maxn],v[maxn],l[maxn],r[maxn],mx=0;
long long s1[maxn],s2[maxn];
long long check(long long x)
{
    long long ret1=0,ret2=0,kr=0;
    for (long long i=1;i<=n;i++)
    {
        if (w[i]>=x) {s1[i]=1;s2[i]=v[i];}
        else {s1[i]=0;s2[i]=0;}
        s1[i]+=s1[i-1];s2[i]+=s2[i-1];
    }
    for (long long i=1;i<=m;i++)
    {
        ret1=(s1[r[i]]-s1[l[i]-1]);
        ret2=(s2[r[i]]-s2[l[i]-1]);
        kr+=ret1*ret2;
    }
    return kr;
}
long long get_ans()
{
    long long l=1,r=mx,ans=inf;
    while (l<=r)
    {
        long long mid=(l+r)>>1;
        long long regis=check(mid);
        ans=min(ans,abs(s-regis));
        if (regis<s) r=mid-1;
        else if (regis>s) l=mid+1;
        else {ans=0;break;}
    }
    return ans;
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&s);
    for (long long i=1;i<=n;i++)
    {
        scanf("%lld%lld",&w[i],&v[i]);
        mx=max(mx,w[i]);
    }
    for (long long i=1;i<=m;i++)
        scanf("%lld%lld",&l[i],&r[i]);
    printf("%lld
",get_ans());
    return 0;
}