WA on #5#6,求调
查看原帖
WA on #5#6,求调
1004245
rich_xty楼主2025/1/28 16:11
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,l,v,cnt,sum,no,ans;
int b[100010];
struct node{int li,ri;};
node a[100010],c[100010];
bool cmp(node x,node y){return x.ri<y.ri;}
void work(){
	cnt=no=ans=sum=0;
	cin>>n>>m>>l>>v;
	for(int i=1;i<=n;i++){
		int di,vi,ai;
		cin>>di>>vi>>ai;
		if(ai==0){
			if(vi>v) 
				a[++cnt].li=di,a[cnt].ri=l;
		}
		else if(ai>0){
			int lft;
			if((v*v-vi*vi)%(ai*2)==0) lft=(v*v-vi*vi)/(ai*2)+di+1;
			else lft=ceil((v*v*1.0-(vi*vi*1.0))/(2*ai*1.0))+di;
			if(lft<0) lft=di-1;
			if(lft<=l) a[++cnt].li=lft,a[cnt].ri=l;
		}
		else{
			if(vi>v){
				int rght;
				if((v*v-vi*vi)%(ai*2)==0) rght=(v*v-vi*vi)/(ai*2)+di-1;
				else rght=floor((v*v*1.0-(vi*vi*1.0))/(2*ai*1.0))+di;
				a[++cnt].li=di,a[cnt].ri=rght;
			}
		}
	}
	for(int i=1;i<=m;i++) cin>>b[i];
	for(int i=1;i<=cnt;i++){
		int lft=lower_bound(b+1,b+1+m,a[i].li)-b;
		int rght=upper_bound(b+1,b+1+m,a[i].ri)-b-1;
		if(lft<=rght) c[++sum].li=lft,c[sum].ri=rght;
	}
	sort(c+1,c+1+sum,cmp);
	sort(b+1,b+1+m);
	for(int i=1;i<=sum;i++){
		if(c[i].li>no){
			ans++;
			no=c[i].ri;
		}
	}
	cout<<sum<<' '<<m-ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>t;
	while(t--) work();
	return 0;
}
2025/1/28 16:11
加载中...