WA on #5 #6 #8 #10 求条
查看原帖
WA on #5 #6 #8 #10 求条
754006
mobaiawa楼主2024/11/8 18:06
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10,M=2e6+10;
ll n,m,L,V;
ll read(){
	ll res=0;bool op=1;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')op^=1;ch=getchar();}
	while('0'<=ch&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
	return op?res:-res;
}
void write(ll x){
	if(x<0){x=-x;putchar('-');}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int p[N]; 
//这里要写一个二分,二分出最左,最右测速仪
pair<int ,int>query(int L,int R){
	int l=0,r=m+1,ans1=0/* 右 */,ans2=2147483640/* 左 */;
	while(r>l){
		int mid=(l+r)>>1;
		if(p[mid]<=R){
			ans1=mid;
			l=mid+1;
		}
		else r=mid;
	}
	l=0,r=m+1;
	while(r>l){
		int mid=(l+r)>>1;
		if(p[mid]>=L){
			ans2=mid;
			r=mid;
		}
		else l=mid+1;
	}
	if(ans1>=ans2&&ans1!=0)return make_pair(ans2,ans1);
	return make_pair(-1,-1);
}
struct node{
	ll first,second;
	bool operator<(const node &y)const{
		if(second==y.second)return first<y.first;
		return second<y.second;
	}
};
node makepair(ll x,ll y){
	node res;
	res.first=x;res.second=y;
	return res;
}
node get(ll d,ll v,ll a,ll L,ll V){//st,ed
	if(a==0){
		if(v>V)return makepair(d,L);//匀速 
		else return makepair(-1,-1);
	}
	else if(a>0){
		if(v>V)return makepair(d,L);
		if(V*V>=v*v+2*a*(L-d))return makepair(-1,-1);
		ll loc=d+ceil(1.0*(V*V-v*v)/(2*a));//匀加速 
		return makepair(loc,L);
	}
	else {
		if(v<=V)return makepair(-1,-1);
		else {
			ll loc=d+floor(1.0*(V*V-v*v)/(2*a));//匀减速 
			return makepair(d,min(L,loc));
		}
	}
}
node dat[N];
void slove(){
	n=read(),m=read(),L=read(),V=read();
	for(int i=1;i<=n;i++){
		ll d=read(),v=read(),a=read();
		node x=get(d,v,a,L,V);//查找超速区间 
		dat[i]=x;//存下超速区间 
	}
	for(int i=1;i<=m;i++)p[i]=read();//这个点有一个测速仪 
	sort(dat+1,dat+1+n);
	sort(p+1,p+1+m);
	p[m+1]=2147483640;
	ll ans1=0,ans2=0;
	for(int i=1,tmp=0;i<=n;i++){
		if(dat[i].first==-1)continue;//没超速 
		ll st=dat[i].first,ed=dat[i].second;//超速区间 
		pair<int,int> res=query(st,ed);
		int l=res.first,r=res.second;//测速仪编号 
		if(r>=l&&r!=-1)ans1++;
		else continue;
		if(i==1||tmp<l){
			tmp=r;
			ans2++;
		}
		else continue;
	}
	
	write(ans1); 
	putchar(' ');
	write(m-ans2);//全部的测速仪减去开了的就是没开的 
	putchar('\n');
}
int main(){
	int T=read();
	while(T--)slove();
	return 0;
} 
2024/11/8 18:06
加载中...