烂代码求条
查看原帖
烂代码求条
886055
MoonCake2011楼主2024/10/28 13:34
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ld long double
int t,n,m,l,vm,d,r,a,p[100005];
struct node{
	int l,r;
	node(int li=0,int ri=0):l(li),r(ri){};
	friend bool operator<(const node&l, const node&r){
		return l.l>r.l;
	}
}pb[100005],sc[100005];
int pbc,scc;
inline void getsq(){
	if(a==0){
		if(r<=vm)return;
		pb[++pbc].l=d;
		pb[pbc].r=l;
	}
	else if(a>0){
		int mxr=r*r+2*a*(d-l);
		if(mxr<=vm*vm)return;
		pb[++pbc].l=d+ceil(((ld)(vm)*vm-(ld)(r)*r)/(2.00*a));
		pb[pbc].r=l;
	}
	else if(a<0){
		if(r<=vm)return;
		pb[++pbc].l=d;
		pb[pbc].r=d+floor(((ld)(vm)*vm-(ld)(r)*r)/(2.00*a));
		pb[pbc].r=min(pb[pbc].r,l);
	}
}
inline bool check(int l,int r){
	int psl=lower_bound(p+1,p+m+1,l)-p;
	int psr=upper_bound(p+1,p+m+1,l)-p-1;
	if(psl>psr) return 0; return 1;
}
set<int>vl; int ni[1000005],nid;
int prx[300005],dp[300005];
inline void tmax(int&l,const int&r){ (l<r)&&(l=r); }
inline void tmin(int&l,const int&r){ (l>r)&&(l=r); }
inline int lb(int v){ return v&~v+1; }
struct bit{
	int val[300005];
	inline void reset(){
		memset(val,0,sizeof val);
	}
	inline void ins(int p,int r){
		for(int i=p;i<=nid;i+=lb(i))
			tmax(val[i],r);
	}
	inline int que(int p){
		int ret=0;
		for(int i=p;i;i-=lb(i))
			tmax(ret,val[i]);
		return ret;
	}
}prb;
struct bit2{
	int val[300005];
	inline void reset(){
		memset(val,0x3f,sizeof val);
	}
	inline void ins(int p,int r){
		for(int i=p;i;i-=lb(i))
			tmin(val[i],r);
	}
	inline int que(int p){
		if(p==0) return 0;
		int ret=0x3f3f3f3f3f3f3f3f;
		for(int i=p;i<=nid;i+=lb(i))
			tmin(ret,val[i]);
		return ret;
	}
}dpb;
signed main(){
	for(cin>>t;t;t--){
		memset(ni,0,sizeof ni);
		cin>>n>>m>>l>>vm;pbc=scc=0;
		vl.clear();nid=0;
		for(int i=1;i<=n;i++)
			cin>>d>>r>>a,getsq();
		for(int i=1;i<=m;++i) cin>>p[i],vl.emplace(p[i]);
		p[m+1]=0x3f3f3f3f;
		for(int i=1;i<=pbc;++i)
			if(check(pb[i].l, pb[i].r))
				sc[++scc]=pb[i],
				vl.emplace(pb[i].l),
				vl.emplace(pb[i].r);
		cout<<scc<<" "; int mxl=0;
		if(scc==0){
			cout<<m<<endl;
			continue;
		}
		for(int tv:vl)ni[tv]=++nid;
		for(int i=1;i<=scc;++i){
			sc[i].l=ni[sc[i].l];
			sc[i].r=ni[sc[i].r];
			prb.ins(sc[i].r+1,sc[i].l);
			tmax(mxl,sc[i].l);
		}
		for (int i=2;i<=nid+1;++i) prx[i]=prb.que(i);
		for(int i=1;i<=m;++i){
			dp[ni[p[i]]]=dpb.que(prx[ni[p[i]]])+1;
			dpb.ins(ni[p[i]],dp[ni[p[i]]]);
		}
		int ans=0x3f3f3f3f3f3f3f3f;
		for(int i=m;i;i--){
			if(ni[p[i]]<mxl) break;
			tmin(ans, dp[ni[p[i]]]);
		}
		cout<<m-ans<<endl;
	}
	return 0;
}
2024/10/28 13:34
加载中...