样例四没过,但是民间数据和Hack都过了
查看原帖
样例四没过,但是民间数据和Hack都过了
596945
nahidaa楼主2024/10/28 14:50
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll NXD,n,m,L,V,mo[100005],qianzhui[1000005],ans;
deque<pair<ll,ll> >dq;
bool o[1000005];
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};
				}
			}
		}
		memset(o,0,sizeof(o));
		memset(qianzhui,0,sizeof(qianzhui));
		for(int i=1;i<=m;++i){
			mo[i]=read();
			o[mo[i]]=1;
		}
		sort(mo+1,mo+m+1);
		qianzhui[0]=o[0];
		for(int i=1;i<=L;++i){
			qianzhui[i]=qianzhui[i-1]+o[i];
		}
		ans=0;
		for(int i=1;i<=n;++i){
			if((d[i].l==d[i].r&&d[i].l==L+1)||d[i].l>L||d[i].l>d[i].r)continue;
			if(d[i].l==0){
				if(qianzhui[d[i].r]!=0){
					ans++;
					d[i].yess=1;
				}
			}else if(qianzhui[d[i].r]!=qianzhui[d[i].l-1]){
				ans++;
				d[i].yess=1;
			}
		}
		sort(d+1,d+n+1,com);
		cout<<ans<<" ";
		while(!dq.empty())dq.pop_back();
		dq.push_back(make_pair(-1,0));
		for(int i=1,j=0;i<=n;++i){
			if(!d[i].yess)continue;
			while(j<m&&mo[j+1]<=d[i].r){
				if(mo[j+1]<d[i].l)j++;
				else{
					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));
				}
			}
			while(dq.front().first<d[i].l)dq.pop_front();
		}
		cout<<m-dq.front().second<<"\n";
	}
	return 0;
}
/*
1
1 1 10 5
0 10 -10000
0


*/
2024/10/28 14:50
加载中...