哪位大佬看看为啥只有30分啊??

P1314 [NOIP2011 提高组] 聪明的质监员

LittleOcean @ 2024-12-06 12:10:20

#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010;
typedef long long LL;
int n,m,s,l=1e9,r=-1;
LL res=0x3f3f3f3f3f3f;
int w[N],v[N],ql[N],qr[N];
LL sumn[N],sumv[N];
LL check(int x){
    for(int i=1;i<=n;i++){
        if(w[i]>=x)sumn[i]=sumn[i-1]+1,sumv[i]=sumv[i-1]+v[i];
        else sumn[i]=sumn[i-1],sumv[i]=sumv[i-1];
    }
    LL y=0;
    for(int i=1;i<=m;i++)y+=(sumn[qr[i]]-sumn[ql[i]-1])*(sumv[qr[i]]-sumv[ql[i]-1]);
    return y;
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&v[i]);
        l=min(l,w[i]);
        r=max(r,w[i]);
    }
    for(int i=1;i<=m;i++)scanf("%d%d",&ql[i],&qr[i]);
    l--,r++;
    while(l+1!=r){
        int mid=(l+r)/2;
        if(check(mid)>=s)l=mid;
        else r=mid;
    }
    cout<<min(abs(check(l)-s),abs(check(r)-s));
}

|