Article From:https://www.cnblogs.com/ErkkiErkko/p/9686719.html

> code:

#include <iostream>
#include <cstdio>
#include <cstdlib>
typedef long long LL;

inline LL read(){
    LL x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x; 
}

const int MAXN=200005;
int n,m;
LL S;
int w[MAXN],v[MAXN],maxw;
int l[MAXN],r[MAXN];
int sum1[MAXN];
LL sum2[MAXN];
LL ans=1e18;

inline bool check(int mid){
    for(int i=1;i<=n;i++){
        if(w[i]>=mid) sum1[i]=1,sum2[i]=v[i];
        else sum1[i]=sum2[i]=0;
        sum1[i]+=sum1[i-1];
        sum2[i]+=sum2[i-1];
    }
    LL temp=0;
    for(int i=1;i<=m;i++)
        temp+=(sum1[r[i]]-sum1[l[i]-1])*(sum2[r[i]]-sum2[l[i]-1]);
    if(llabs(temp-S)<ans) ans=llabs(temp-S);
    return temp>=S;
}

int main(){
    n=read(),m=read(),S=read();
    for(int i=1;i<=n;i++)
        maxw=std::max(maxw,w[i]=read()),v[i]=read();
    for(int i=1;i<=m;i++)
        l[i]=read(),r[i]=read();
    int ll=1,rr=maxw+1;
    while(ll<=rr){
        int mid=((ll+rr)>>1);
        if(check(mid)) ll=mid+1;
        else rr=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *