第8和13个数据有毒

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,w[200010],v[200010],q[200010][2]={0},mx=0,mn;
int num[200010],value[200010];
long long s,ans=(0x7fffffffffffffffll)>>1;
inline int getint()
{
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    int res=0;
    while(c>='0'&&c<='9')
    {
        res=res*10+(c-'0');
        c=getchar();
    }
    return res;
}

inline long long abs(long long a)
{
    if(a>0) return a;
    else return -a;
}

long long cal(int l,int r)
{
    return (num[r]-num[l-1])*(value[r]-value[l-1]);
}

long long sieve(int x)
{
    long long res=0;
    num[0]=value[0]=0;
    for(int i=1;i<=n;++i)
    {
        num[i]=num[i-1];
        value[i]=value[i-1];
        if(w[i]>=x)
        {
            num[i]++;
            value[i]+=v[i];
        }
    }
    for(int i=1;i<=m;++i) res+=cal(q[i][0],q[i][1]);
    return res;
}

void binary_search(int l,int r)
{
    while(l<r)
    {
//      cout<<l<<' '<<r<<endl;
        int mid=(l+r)>>1;
        long long temp=sieve(mid);
//      cout<<temp<<endl;
        long long val=abs(s-temp);
//      cout<<val<<endl;
        if(temp<s) r=mid;
        else l=mid+1;
        if(ans>val) ans=val;
//      cout<<endl;
    }
    printf("%lld\n",ans);
    return;
}

int main()
{
    scanf("%d%d%lld",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
        w[i]=getint(),v[i]=getint();
        if(w[i]>mx) mx=w[i]+1;
    } 
    for(int i=1;i<=m;++i) q[i][0]=getint(),q[i][1]=getint();
//  for(int i=1;i<=n;++i) cout<<w[i]<<' '<<v[i]<<endl;
//  for(int i=1;i<=m;++i) cout<<q[i][0]<<' '<<q[i][1]<<endl;
    binary_search(mn,mx);\
    getchar(),getchar();
    return 0;
}不懂啊,死活Ac不了这两个点

1 条评论

  • 1

信息

ID
1740
难度
7
分类
其他 | 二分查找 点击显示
标签
递交数
4083
已通过
851
通过率
21%
被复制
13
上传者