求助,25分,de不出bug

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

又菜又爱玩 @ 2021-12-26 10:57:06

#include<stdio.h>
#include<algorithm>
#include<math.h>
#define N 200005
using namespace std;
long long w[N],v[N],l[N],r[N],qn[N],qv[N],sum;
long long n,m,s,W=0,maxx;
bool check(long long mid)
{
    int y=0;
    for(int i=1;i<=N-1;i++)
    {
        qn[i]=0;
        qv[i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=mid)
        {
            qn[i]=qn[i-1]+1;
            qv[i]=qv[i-1]+v[i];
        }
        else
        {
            qn[i]=qn[i-1];
            qv[i]=qv[i-1];
        }
    }
    for(int i=1;i<=m;i++)
    {
        y=y+(qn[r[i]]-qn[l[i]-1])*(qv[r[i]]-qv[l[i]-1]);
    }
    sum=abs(y-s);
    if(y>s)
    return 1;
    return 0;

}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&w[i],&v[i]);
        maxx=max(maxx,w[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&l[i],&r[i]);
    }
    long long ans=2e18;
    long long low=0;
    long long high=maxx+2;
    while(low<=high)
    {
        long long mid=(low+high)/2;
        if(check(mid))
        {
            low=mid+1;
            W=mid;
        }
        else
        {
            high=mid-1;
        }
        ans=min(sum,ans);
    }
    printf("%lld",ans);
    return 0;
}

|