85分代码,求助。

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

Milk_Feng @ 2019-04-30 20:22:49

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define Reg register
using namespace std;
int lef[100050],rig[100050],num[100050];
long long n,m,s,ans,tot=0x7ffffffffff,maxx;
long long wos[100050],val[100050],sum[100050];
inline long long max(long long x,long long y) {return x>y?x:y;}
inline long long min(long long x,long long y) {return x<y?x:y;}
inline long long abc(long long x) {return x>=0?x:(-x);}
inline long long js(int x)
{
    long long ans=0;
    memset(sum,0,sizeof(sum));
    memset(num,0,sizeof(num));
    for(Reg int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]; num[i]=num[i-1];
        if(wos[i]>=x) sum[i]+=val[i],num[i]++;
    }
    for(Reg int i=1;i<=m;i++)
    {
        int l=lef[i],r=rig[i];
        ans+=(long long)(num[r]-num[l-1])*(sum[r]-sum[l-1]);
    }
    return ans;
}
inline bool judge(int x)
{
    long long ans=js(x);
    tot=min(tot,abc(ans-s));
    if(ans>s) return 1;
    else if(ans<s) return 0;
    else return 2;
}
inline int erfen(long long l,long long r)
{
    if(l==r) return l;
    long long mid=(l+r)>>1;
    int jud=judge(mid);
    if(jud==0) return erfen(l,mid);
    else if(jud==1) return erfen(mid+1,r);
    else return mid;
}
int main()
{
    cin>>n>>m>>s;
    for(Reg int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&wos[i],&val[i]);
        maxx=max(maxx,wos[i]);
    }
    for(Reg int i=1;i<=m;i++) scanf("%d%d",&lef[i],&rig[i]);
    int ans=erfen(1,maxx); tot=min(tot,abc(s-js(ans)));
    cout<<tot;
    return 0;
}

85分代码, 求dalao帮忙。。


|