蒟蒻拿到了90分,WA了#10测试点,全程整数,求调
查看原帖
蒟蒻拿到了90分,WA了#10测试点,全程整数,求调
1417582
De___Bruyne楼主2024/10/27 01:04

赛时样例都过了,但是没过这个的#10
蒟蒻的我难受了

#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+10;
int T;
int n,m,L,V,r,numsxt,nc;
struct car{
	int d,v,a;
}cars[N];
int p[N],idqj;
pii qj[N];
bool cmpp(pii a,pii b){
	if(a.first!=b.first)return a.first<b.first;
	return a.second<b.second;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
//	freopen("detect.in","r",stdin);
//	freopen("detect.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>m>>L>>V;
		for(int i=1;i<=n;i++)cin>>cars[i].d>>cars[i].v>>cars[i].a;
		for(int i=1;i<=m;i++)cin>>p[i];
		r=1,numsxt=0,nc=0,idqj=0;
		for(int i=1;i<=n;i++){
			if(cars[i].d>p[m])continue;
			if(cars[i].a==0&&cars[i].v>V){
				nc++;
				r=lower_bound(p+r,p+1+m,cars[i].d)-p;
				continue;
			}
			if(cars[i].a>0){
				if(1LL*cars[i].v*cars[i].v+2LL*cars[i].a*(p[m]-cars[i].d)>V*V)nc++;
				else continue;
				int mid,ll=0,rr=m;
				while(ll<rr){
					mid=(ll+rr)>>1;
					if(1LL*cars[i].v*cars[i].v+2LL*cars[i].a*(p[mid]-cars[i].d)>V*V)rr=mid;
					else ll=mid+1;
				}
				r=max(r,rr);
			}
			if(cars[i].a<0){
				int ll=lower_bound(p+1,p+1+m,cars[i].d)-p;
				if(cars[i].v*cars[i].v+2LL*cars[i].a*(p[ll]-cars[i].d)>V*V){
					nc++;
					int mid,le=ll,rr=m;
					while(le<rr){
						mid=(le+rr+1)>>1;
						if(cars[i].v*cars[i].v+2LL*cars[i].a*(p[mid]-cars[i].d)>V*V)le=mid;
						else rr=mid-1;
					}
					qj[++idqj]=mp(ll,rr);
				}
			}
		}
		qj[++idqj]=mp(r,m);
		sort(qj+1,qj+idqj,cmpp);
		int rr=0;
		for(int i=1;i<=idqj;i++){
			if(qj[i].first>rr){
				numsxt++;
				rr=qj[i].second;
			}
			rr=min(rr,qj[i].second);
		}
		if(!idqj)numsxt=1;
		if(nc==0)numsxt=0;
		cout<<nc<<' '<<m-numsxt;
		if(T)cout<<'\n';
	}
	cout<<endl;
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
2024/10/27 01:04
加载中...