关于40pts
查看原帖
关于40pts
1379399
reductt楼主2024/10/27 11:53

rt,我是40pts,求问是不是被卡精度了,而且最后几个大样例都是正好多一个或少一个。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOR_(i,a,b) for(int i=b;i>=a;i--)
#define fir first
#define sec second
#define pb push_back
namespace FastIO{
	int buf[100]={0},p=0;
	int rd(){
		int x=0,f=1;char c=getchar();
		while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
		while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
		return x*f;
	}void write(int x,char c='#'){
		if(!x)putchar('0');
		else{
			if(x<0)putchar('-'),x*=-1;
			while(x)buf[++p]=x%10,x/=10;
			while(p)putchar(buf[p--]+'0');
		}
		if(c!='#')putchar(c);
	}
};
#define rd FastIO::rd
#define write FastIO::write
typedef __int128 u128;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long double ld;
const int N=1e5+10,M=1e6+10;
struct Car{int d,v,a;}cars[N];
struct Range{int l,r;}ranges[N];
struct DS{
	int c[M],tot;
	void clear(){memset(c,0,sizeof(c));}
	#define lowbit(x) (x&(-x))
	void add(int i,int k){
		i++;
		while(i<M)c[i]+=k,i+=lowbit(i);
	}int query(int i){
		i++,tot=0;
		while(i)tot+=c[i],i-=lowbit(i);
		return tot;
	}int query(int l,int r){
		if(l<=0)return query(r);
		return query(r)-query(l-1);
	}
	#undef lowbit
}ds,ds1;
int n,m,L,V,p[N];
pii clac(int d,int v,int a){
	if(a==0){
		if(v>V)return {d,L};
		else return {-1,-1};
	}else if(a>0){
		if(v>V)return {d,L};
		else{
			ld t=1.0*(V-v)/a;
			int dd=(int)(v*t+a*t*t/2+0.9999999);
			return {min(d+dd,L),L}; 
		}
	}else if(a<0){
		a*=-1;
		if(v<=V){
			ld t=1.0*v/a;
			int dd=(int)(v*t+a*t*t/2);
			return {d,min(d+dd,L)};
		}else{
			ld t=1.0*(v-V)/a;
			int dd=(int)(v*t-a*t*t/2);
			return {d,min(d+dd,L)};
		}
	}
	return {-1,-1};
}
void init(){ds.clear(),ds1.clear();}
void solve(){
	init();
	n=rd(),m=rd(),L=rd(),V=rd();
	FOR(i,1,n){
		int d=rd(),v=rd(),a=rd();
		pii p=clac(d,v,a);
		cars[i]={d,v,a},ranges[i]={p.fir,p.sec};
	}
	FOR(i,1,m)p[i]=rd(),ds.add(p[i],1);
	int ans1=0,tot=0,ans2=0;
	FOR(i,1,n){
		int l=ranges[i].l,r=ranges[i].r;
		if(ds.query(l,r))ans1++;
//		printf("[%lld,%lld]\n",l,r);
	}
	write(ans1,' ');
	FOR(i,1,n){
		int l=ranges[i].l,r=ranges[i].r;
		if((l<0&&r<0)||!ds.query(l,r))continue;
		ranges[++tot].l=lower_bound(p+1,p+m+1,l)-p;
		ranges[tot].r=upper_bound(p+1,p+m+1,r)-p-1;
//		printf("[%lld,%lld]\n",ranges[tot].l,ranges[tot].r);
	}
	sort(ranges+1,ranges+tot+1,[&](Range r1,Range r2){return (r1.r!=r2.r)?r1.r<r2.r:r1.l<r2.l;});
//	cerr<<"#\n";
//	FOR(i,1,tot)printf("[%lld,%lld]\n",ranges[i].l,ranges[i].r);
	FOR(i,1,tot){
		int l=ranges[i].l,r=ranges[i].r;
		if(ds1.query(l,r))continue;
		ds1.add(r,1),ans2++;
	}
	write(m-ans2,'\n');
}
signed main(){
//	freopen("detect4.in","r",stdin),freopen("detect.out","w",stdout);
	int T=rd();
	while(T--)solve();
	return 0;
}
2024/10/27 11:53
加载中...