rt

TLE on #10

码风有点史，见谅

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<stack>
#include<queue>
#define debug() cout<<"qwq"<<endl
using namespace std;

const int N=100010;

int a[N],d[N],p[N],v[N];
int T;
int n,m,L,V;
bool inclued[N];

struct node{
	int lpt,rpt;
}cars[N];

bool cmp(node x,node y)
{
	if(x.lpt==y.lpt) return x.rpt>y.rpt;
	return x.lpt<y.lpt;//警钟长鸣
}

inline int read()
{
	int x=0,f=1;char ch=getchar_unlocked();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar_unlocked();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar_unlocked();}
	return x*f;
}

inline void write(int x)
{
	
	if (!x)
	{
		putchar('0');
		return;
	}
	int len = 0, k1 = x, c[40];
	if (k1 < 0) k1 = -k1, putchar_unlocked('-');
	while (k1) c[len ++ ] = k1 % 10 ^ 48, k1 /= 10;
	while (len -- ) putchar_unlocked(c[len]);
}

int main()
{
//	freopen("detect.in","r",stdin);
//	freopen("detect.out","w",stdout);
	
	T=read();
	int l,r;
	while(T--)
	{
		n=read();
		m=read();
		L=read();
		V=read();
		for(int i=1;i<=n;i++)
		{
			d[i]=read();
			v[i]=read();
			a[i]=read();
		}
		for(int i=1;i<=m;i++) p[i]=read();
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]<=0 && v[i]<=V) continue;//如果刚开始就不超速，并且速度越来越低，就不用考虑
			if(a[i]<=0)
			{
				l=1,r=m;
				int idx=0;
				while(l<=r)//找到遇到的第一个加速仪，作为区间的左端点(此时必定会超速，如果不超速会在最后的if被continue掉)
				{
					int mid=(l+r)>>1;
					if(p[mid]>=d[i]) 
					{
						r=mid-1;
						idx=mid;
					}else l=mid+1;
				}
				if(idx==0) continue;
				l=idx,r=m;
				int ans=0;
				while(l<=r)//找到最后一个会被判定为超速的测速仪，作为超速区间的右端点
				{
					int mid=(l+r)>>1;
					long double vi=sqrt(v[i]*v[i]*1.0+2.0*a[i]*(p[mid]-d[i]));
					if(vi>V) 
					{
						l=mid+1;
						ans=mid;
					}else r=mid-1;
				}
				if(ans<idx) continue;
				cars[++sum].lpt=idx,cars[sum].rpt=ans;
			}else{
				int detectidx=V*V-v[i]*v[i];
				detectidx/=(2*a[i]);
				detectidx+=d[i];//算出超速的位置
				if(v[i]>V) detectidx=d[i]-1;//一直都超速
				int ans=0;
				l=1,r=m;
				while(l<=r)//查找到第一个会判定该车超速的摄像头
				{
					int mid=(l+r)>>1;
					if(p[mid]>detectidx) 
					{
						r=mid-1;
						ans=mid;
					}else l=mid+1;
				}
				if(ans==0) continue;
				cars[++sum].lpt=ans,cars[sum].rpt=m;//对于一个在第idx个位置检测到超速，且加速度>0的车，超速区间为idx到道路尽头
			}
		}
		sort(cars+1,cars+sum+1,cmp);
		int mr=1000000;
		for(int i=sum;i>=1;i--)//排除无用的区间（被包含的区间）
		{
			if(mr<=cars[i].rpt) inclued[i]=true;
			if(mr>cars[i].rpt) mr=cars[i].rpt;
		}
		int ans=0,rpoint=0;
		for(int i=1;i<=sum;i++)
		{
			if(inclued[i])
			{
				inclued[i]=false;
				continue;
			}
			if(rpoint<cars[i].lpt)
			{
				ans++;
				rpoint=cars[i].rpt;
			}
		}
		write(sum);
		printf(" ");
		write(m-ans);
		printf("\n");
	}
	return 0;
}