90分Wa#10,#13求助

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

LINdx @ 2022-07-12 19:03:20

#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e5;
struct node
{
    int v,w; 
}A[maxn];
int l[maxn],r[maxn];
long long sum[maxn];
long long val[maxn];
int n,m;
long long s;
long long ans;
long long mi(long long x,long long y)
{
    if(x<y)return x;
    else return y;
}
void nn(int now)
{
    ans=sum[0]=val[0]=0;
    for(int i=1;i<=n;i++)
    {
        if(A[i].w>=now)
        sum[i]=sum[i-1]+1,val[i]=val[i-1]+A[i].v;
        else sum[i]=sum[i-1],
        val[i]=val[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        long long k1=sum[r[i]]-sum[l[i]-1];
        long long k2=val[r[i]]-val[l[i]-1];
        ans+=(k1*k2);
    }
}
int main()
{

    scanf("%d%d%lld",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&A[i].w,&A[i].v);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l[i],&r[i]);
    }
    int left=0,right=1e6+10;
    while(left<=right)
    {
        int mid=(left+right)/2;
        nn(mid);
        if(ans>=s)left=mid;
        else right=mid;
        if(abs(left-right)==1)
        {
            nn(left);
            long long k1=ans;
            nn(right);
            long long k2=ans;
            ans=mi(abs(k1-s),abs(k2-s));
            break;
        }
    }
    printf("%lld",ans);
    return 0;
 } 

有没有大佬解释一下为何只有90分,Wa掉#10,#13 调了一个下午


by LINdx @ 2022-07-12 19:03:40

谢谢大佬们


by LINdx @ 2022-07-12 20:29:45

已经A了 数组太小


|