关于赛时调了2h+才调过大样例,赛后重写的代码只得80pts
查看原帖
关于赛时调了2h+才调过大样例,赛后重写的代码只得80pts
856459
yangjunhan1楼主2024/10/27 13:54

求大佬看看哪有问题,调了半天了,不过第五个大样例

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n,m,L,V,v,d,a,p[N],ans1,ans2,l[N],r[N],lst,cnt;
struct qp{
    int ls,rs;
}car[N];
int f1(int x){
    int l=1,r=m,res=m+1;
    while(l<=r){
        int mid=l+r>>1;
        if(p[mid]>=x){
            res=mid;
            r=mid-1;
        }
        else    l=mid+1;
    }
    return res;
}
int f2(int x){
    int l=1,r=m,res=0;
    while(l<=r){
        int mid=l+r>>1;
        if(p[mid]<=x){
            res=mid;
            l=mid+1;
        }
        else    r=mid-1;
    }
    return res;
}
bool cmp(qp a,qp b){
    return a.ls==b.ls?a.rs<b.rs:a.ls<b.ls;
}
int main(){
    // freopen("detect5.in","r",stdin);
    // freopen("detect.out","w",stdout);
    cin>>T;
    while(T--){
        for(int i=1;i<=n;i++)   car[i].ls=car[i].rs=0;
        ans1=ans2=cnt=0;
        memset(l,-1,sizeof l);
        memset(r,-1,sizeof r);
        cin>>n>>m>>L>>V;
        for(int i=1;i<=n;i++){
            cin>>d>>v>>a;
            if(!a){
                if(v>V) l[i]=d,r[i]=L;
                continue;
            }
            if(a>0){
                if(v>V){
                    l[i]=d;
                    r[i]=L;
                    continue;
                }
                l[i]=d+(V*V-v*v)/2/a+1;
                r[i]=L;
                if(l[i]>r[i])   l[i]=r[i]=-1;
            }
            if(a<0){
                if(v<=V) continue;
                l[i]=d;
                r[i]=d+(V*V-v*v)/2/a;
                if(l[i]>r[i])   l[i]=r[i]=-1;
            }
        }
        for(int i=1;i<=m;i++)   cin>>p[i];
        for(int i=1;i<=n;i++){
            if(l[i]==r[i] && l[i]==-1)  continue;
            int nl=f1(l[i]);
            int nr=f2(r[i]);
            if(nl<=nr){
                ans1++;
                car[++cnt]={nl,nr};
            }
        }
        lst=-1;
        sort(car+1,car+1+cnt,cmp);
        for(int i=1;i<=n;i++){
            int nl=car[i].ls,nr=car[i].rs;
            if(nl==nr && !nl)   continue;
            if(nl<=lst && lst<=nr)  continue;
            if(nl>lst) ans2++;
            lst=nr;
        }
        cout<<ans1<<" "<<m-ans2<<endl;
    }
    return 0;
}
//g++ detect.cpp -O2 -std=c++14 -Wall -o detect
2024/10/27 13:54
加载中...