MnZn求助P1314

做法：二分加前缀和。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,s,w[200010],v[200010],sumw[200010],sumv[200010],r[200010],l[200010];
ll minn=1e18,maxn=-1e18;
ll ans=1e18,sum;
bool check(int wans){
    sum=0;
    memset(sumw,0,sizeof(sumw));
    memset(sumv,0,sizeof(sumv));
    for(int i=1;i<=n;i++){
        if(w[i]>=wans){
            sumw[i]=sumw[i-1]+1;
            sumv[i]=sumv[i-1]+v[i];
        }
        else{
            sumw[i]=sumw[i-1];
            sumv[i]=sumv[i-1];
        }
    }
    for(int i=1;i<=m;i++){
        sum+=(sumw[r[i]]-sumw[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
    }
    sum=llabs(sum-s);
    if(sum>s){
        return true;
    }
    return false;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
        minn=min(minn,w[i]);
        maxn=max(maxn,w[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>l[i]>>r[i];
    }
    int l1=minn-1,r1=maxn+2;
    while(l1!=r1){
        int mid=(l1+r1)/2;
        if(check(mid)){
            l1=mid+1;
        }
        else{
            r1=mid;
        }
        ans=min(sum,ans);
    }
    cout<<ans<<endl;
    return 0;
}

蒟蒻代码调试能力太差了，求调QAQ