Rt.

CSP-S 2024 T2 代码:

#include <bits/stdc++.h>
using namespace std;
int t,n,m,tot,ans,mxp;
double mx,len,p[100100];
array<double,2> car[100100];
const double eps=0.0000000001,inf=1e9;
vector<array<double,2>> seg;
bool ok[100100];
void work(){
	tot=ans=mxp=0,seg.clear();
	scanf("%d%d%lf%lf",&n,&m,&len,&mx);
	for(int i=1;i<=n;i++){
		double pos,spe,add;
		scanf("%lf%lf%lf",&pos,&spe,&add);
		if(add==0.0){
			if(spe<=mx) continue; 
			seg.push_back({pos,len});
//			printf("! %.15f %.15f\n",pos,len);
		}else if(add>0.0){
			if(spe>mx){
//				printf("@ %.15f %.15f\n",pos,len);			
				seg.push_back({pos,len});
			}else{
				if(pos+(mx*mx-spe*spe)/(2*add)+eps<=len){
//					printf("# %.15f %.15f\n",pos+(mx*mx-spe*spe)/(2*add)+eps,len);
					seg.push_back({pos+(mx*mx-spe*spe)/(2*add)+eps,len});
				}
			} 
		}else if(add<0.0){
			if(spe<=mx) continue;
//			printf("$ %.15f %.15f\n",pos,min(pos+(mx*mx-spe*spe)/(2*add)-eps,len));
			seg.push_back({pos,min(pos+(mx*mx-spe*spe)/(2*add)-eps,len)});
		}
	}
	p[0]=(-inf),p[m+1]=inf;
	for(int i=1;i<=m;i++){
		scanf("%lf",&p[i]);
	}
	for(int i=1;i<=m;i++) ok[i]=true;
	for(auto sg:seg){
		int idx=lower_bound(p+0,p+m+2,sg[0])-p;
		if(p[idx]<=sg[1]){
			car[++tot]=sg;
		}
	}
	for(int i=1;i<=tot;i++){
		swap(car[i][0],car[i][1]);
	}
	sort(car+1,car+tot+1);
	for(int i=1;i<=tot;i++){
		swap(car[i][0],car[i][1]);
//		printf("%.15f %.15f\n",car[i][0],car[i][1]);
	}
	for(int p1=1,p2=0;p1<=tot;p1++){
		if(p[p2]<car[p1][0]){	
			while(p2+1<=m&&p[p2+1]<=car[p1][1]) p2++;
		}
		ok[p2]=false;
	}
	for(int i=1;i<=m;i++) ans+=ok[i];
	printf("%d %d\n",tot,ans);
}
int main(){
// 	freopen("detect.in","r",stdin);
// 	freopen("detect.out","w",stdout);
	scanf("%d",&t);
	for(;t--;) work();
}

*此代码在洛谷可以通过民间数据

CCF的测评机应该比洛谷强