只AC了第一个点其它Wa,求调QAQ
查看原帖
只AC了第一个点其它Wa,求调QAQ
764455
HAPPYspider楼主2025/1/20 22:35

rt.

#include<bits/stdc++.h>
using namespace std;

#define int long long

int n,L,sum;
int tag[50005];

struct cow{
    int w,x,d;
};
cow a[50005];
bool cmp(cow a,cow b){
    return a.x<b.x;
}

bool check(int t){
    int l=1,r=n,s=0;
    for(int i=1;i<=n;i++){
        if(a[i].d==1){
            if(a[i].x+t>=L)s+=a[r--].w;
        }else{
            if(a[i].x-t<=0)s+=a[l++].w;
        }    
        return s*2>=sum;
    }
}



signed main(){
    scanf("%lld%lld",&n,&L);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&a[i].w,&a[i].x,&a[i].d);
        sum+=a[i].w;
    }
    sort(a+1,a+n+1,cmp);
    int l=0,r=1e9;//二分时间
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid;
    }
    int time=r;
    int ans=0;
    int k=0;
    for(int i=1;i<=n;i++){
        if(a[i].d==-1){
            int pos=a[i].x-time*2;//相对速度为2?
            l=0,r=k+1;//二分相遇牛数量
            while (l+1<r)
            {
                int mid=(l+r)>>1;
                if(tag[mid]>=pos)r=mid;
                else l=mid;
            }
            ans+=k-r+1;
        }else{
            tag[++k]=a[i].x;//前k头牛位置
        }
    }
    printf("%lld",ans);
    return 0;
}
2025/1/20 22:35
加载中...