蒟蒻求助

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

C202216chenyuxiao @ 2020-02-27 15:56:54

#include<cstdio>
#include<cmath>
#define MAXN 2000005
const long long INF=1e20; 
long long n,m,s,w[MAXN],v[MAXN],l[MAXN],r[MAXN],sumv[MAXN],sumn[MAXN];
long long maxx,minn=INF,ans=INF;
long long Y(long long m1) {
    long long ans1=0;
    for(long long i=1;i<=n;i++)
    {
        if(w[i]>=m1)
        {
            sumv[i]=sumv[i-1]+v[i];
            sumn[i]=sumn[i-1]+1;
        }
        else
        {
            sumv[i]=sumv[i-1];
            sumn[i]=sumn[i-1];
        }
    }
    for(int i=1;i<=m;i++)
    {
        ans1+=(sumn[r[i]]-sumn[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]); 
    }
    return ans1;
}
int main()
{
    scanf("%lld %lld %lld", &n, &m, &s);
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld %lld", &w[i], &v[i]);
        if(w[i]>maxx)
        {
            maxx=w[i];
        }
        if(w[i]<minn)
        {
            minn=w[i];
        }
    }
    for(long long i=1;i<=m;i++)
    {
        scanf("%lld %lld", &l[i], &r[i]);
    }
    long long l=minn-1,r=maxx+2;
    while(l<=r)
    {
        long long mid=(l+r)/2,t=Y(mid),low=abs(s-t);
        if(t>s)
        {
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
        if(low<ans)
        {
            ans=low;
        }
    }
    printf("%lld", ans);
    return 0;
}

为什么只有45分其他的全部WA


|