70求助TLE

beargeng是女孩子 @ 2019-02-16 17:39:07

// luogu-judger-enable-o2
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int NR=210000;
const int MAXW=1100000;
long long S;
int n,m;
int w[NR],v[NR],ql[NR],qr[NR];
long long sumn[NR],sumv[NR];
inline void read(int &k)
{
    long long x=0,y=1;
    char c=getchar();
    while(c>'9'||c<'0') 
    { 
        if(c=='-')
        y=-1; 
        c=getchar(); 
    }
    while(c>='0'&&c<='9') 
    { 
        x=x*10+c-'0';
        c=getchar();
    }
    k=x*y;
}
long long cc(int x)
{
    long long all=0; 
    for(int i=1;i<=m;i++)
    {
        long long c1=0,c2=0;
        for(int j=ql[i];j<=qr[i];j++)
        {
            if(w[j]>=x)
            {
                c1++;
                c2+=v[j]; 
            }
        }
        all+=c1*c2;
    }
    return all;
}
bool check(int x)
{
    return cc(x)>=S;
}
int main()
{
    read(n);
    read(m);
    cin>>S;
    for(int i=1;i<=n;i++)
    {
        read(w[i]);
        read(v[i]);
    }
    for(int i=1;i<=m;i++)
    {
        read(ql[i]);
        read(qr[i]);
    }
    int l=MAXW,r=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        l=min(w[i],l);
        r=max(w[i],r);
    }
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(check(m)) ans=m,l=m+1; 
        else r=m-1;
    }
    cout<<min(abs(cc(ans)-S),abs(cc(ans+1)-S))<<endl;
    return 0;
}

by ousuimei_68 @ 2019-02-16 17:42:35

tql

by lemondinosaur @ 2019-02-16 17:44:45

不应该直接求区间可以用前缀和

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=200011; struct rec{int w,v;}a[N];
int n,m,l[N],r[N],c[N],d[N]; long long b[N],stdd;
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=ans*10+(c-48),c=getchar();
    return ans;
}
inline long long check(int mid){
    rr long long ans=-stdd;
    for (rr int i=1;i<=n;++i) b[i]=b[i-1]+a[i].v*(a[i].w>=mid);
    for (rr int i=1;i<=n;++i) c[i]=c[i-1]+(a[i].w>=mid);
    for (rr int i=1;i<=m;++i) ans+=(b[r[i]]-b[l[i]-1])*(c[r[i]]-c[l[i]-1]);
    return ans;
}
signed main(){
    n=iut(); m=iut(); scanf("%lld",&stdd);
    for (rr int i=1;i<=n;++i) a[i]=(rec){iut(),iut()};
    for (rr int i=1;i<=m;++i) l[i]=iut(),r[i]=iut();
    for (rr int i=1;i<=n;++i) d[i]=a[i].w;
    sort(d+1,d+1+n); rr int tt=unique(d+1,d+1+n)-d-1;
    rr int L=1,R=tt+1; rr long long minx=1e18;
    while (L<R){
        rr int mid=(L+R)>>1; rr long long t=check(d[mid]);
        if (t<=0) R=mid; else L=mid+1; t=t<0?-t:t;
        minx=minx<t?minx:t;
    }
    return !printf("%lld",minx);
}

by lemondinosaur @ 2019-02-16 17:45:46

代码丑陋，敬请谅解 @WA我最强

by beargeng是女孩子 @ 2019-02-16 17:50:30

@ousuimei_68 orz

by beargeng是女孩子 @ 2019-02-16 17:50:59

@SSL_XJQ_逐风之刃 非常感谢，我改一下二分检查函数

by lemondinosaur @ 2019-02-16 17:57:53

好的