样例四没过,但是民间数据和Hack都过了
查看原帖
样例四没过,但是民间数据和Hack都过了
596945
nahidaa楼主2024/10/29 14:19
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll NXD,n,m,L,V,mo[100005],ans;
deque<pair<ll,ll> >dq;
struct carr{
	ll wei,v,a;
}c[100005];
struct qu{
	ll l,r,yess;
}d[100005];
ll read(){
	ll x=0,sign=1;
	char c=getchar();
	while(!(c>='0'&&c<='9')){
		if(c=='-')sign=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*sign;
}
bool com(const qu& x,const qu& y){
	if(x.r!=y.r)return x.r<y.r;
	return x.l<y.l;
}
int main()
{
	freopen("detect4.in","r",stdin);
	NXD=read();
	for(int RP=1;RP<=NXD;RP++){
		n=read(),m=read(),L=read(),V=read();
		for(int i=1;i<=n;++i){
			c[i]=(carr){read(),read(),read()};
			if(c[i].v>V){
				if(c[i].a>=0){
					d[i]=(qu){c[i].wei,L,0};
				}else{
					d[i]=(qu){c[i].wei,min(L,c[i].wei+(-V*V+c[i].v*c[i].v-1)/(-2*c[i].a)),0};
				}
			}else{
				if(c[i].a<=0){
					d[i]=(qu){L+1,L+1,0};
				}else{
					d[i]=(qu){c[i].wei+(V*V-c[i].v*c[i].v-1)/(2*c[i].a)+1,L,0};
				}
			}
		}
		for(int i=1;i<=m;++i){
			mo[i]=read();
		}
		sort(mo+1,mo+m+1);
		sort(d+1,d+n+1,com);
		while(!dq.empty())dq.pop_back();
		dq.push_back(make_pair(-1,0));
		ans=0;
		for(int i=1,j=0;i<=n;++i){
			while(j<m&&mo[j+1]<=d[i].r){
				j++;
				ll wei=mo[j],ge=dq.front().second+1;
				while(dq.back().second>=ge){
					dq.pop_back();
				}
				dq.push_back(make_pair(wei,ge));
			}
			if(dq.back().first<d[i].l||d[i].l>d[i].r||(d[i].l==L+1&&d[i].l==d[i].r)){
				continue;
			}
			ans++;
			while(dq.front().first<d[i].l)dq.pop_front();
		}
		cout<<ans<<" ";
		cout<<m-dq.front().second<<"\n";
	}
	return 0;
}
/*


*/
2024/10/29 14:19
加载中...