求调
查看原帖
求调
1252050
zyc230808chenwei楼主2024/11/24 20:25
#include<bits/stdc++.h>
using namespace std;

struct node{
	int d,v,a;
}c[100005];
struct tree{
	int l,r,f;
}t[100005];
int n,m,L,V,cnt,sum,bl,T,o;
int jl[100005],Lj[1000005];
bool cmp1(tree x,tree y){
	return x.f<y.f;
}
bool cmp2(tree x,tree y){
	return x.r<y.r || (x.r==y.r && x.l>y.l);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		memset(Lj,0,sizeof(Lj)); 
		memset(t,0,sizeof(t)); 
		memset(jl,0,sizeof(jl)); 
		memset(c,0,sizeof(c)); 
		sum=0,cnt=0,bl=0;
		cin>>n>>m>>L>>V;
		for(int i=1;i<=n;i++) cin>>c[i].d>>c[i].v>>c[i].a;
		for(int i=1;i<=n;i++){
			if(c[i].a>0){
				if(c[i].v>V){
					t[++cnt].l=c[i].d;
					t[cnt].r=L;
				}else{
					int lt=c[i].d+int(1.0*(c[i].v*(1.0*(V-c[i].v)/c[i].a))+c[i].a*(1.0*(V-c[i].v)/c[i].a)*(1.0*(V-c[i].v)/c[i].a)/2+1);
					if(lt<=L){
						t[++cnt].l=lt;
						t[cnt].r=L;
					}
				}
			}else if(c[i].a==0){
				if(c[i].v>V){
					t[++cnt].l=c[i].d;
					t[cnt].r=L;
				}
			}else {
				if(c[i].v>V){
					int rt=c[i].d+int(1.0*(c[i].v*(1.0*(V-c[i].v)/c[i].a))+c[i].a*(1.0*(V-c[i].v)/c[i].a)*(1.0*(V-c[i].v)/c[i].a)/2);
					rt=min(rt,L);
					t[++cnt].r=rt;
					t[cnt].l=c[i].d;
				}
			}
		}
		sum=cnt;
		for(int i=1;i<=m;i++) cin>>o,Lj[o]=o;
		for(int i=1;i<=L;i++){
			if(!Lj[i]) Lj[i]=Lj[i-1];
		}
		for(int i=1;i<=cnt;i++){
			if(Lj[t[i].r]==Lj[t[i].l-1])
				sum--,t[i].f=1;
		}
		sort(t+1,t+cnt+1,cmp1);
		sort(t+1,t+sum+1,cmp2);
		for(int i=1;i<=sum;i++){
			bool F=1;
			for(int j=bl;j>=1;j--){
				if(jl[j]<=t[i].r && jl[j]>=t[i].l){
					F=0;
					break;
				}
			}
			if(F){
				jl[++bl]=Lj[t[i].r];
			}
		}
		cout<<sum<<" "<<m-bl<<"\n";
	}
	return 0;
}
2024/11/24 20:25
加载中...