这常数能过官方数据吗?
查看原帖
这常数能过官方数据吗?
1224325
Mark_oy楼主2024/10/28 16:00
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+11;
const int INF=1e9;
#define ls p<<1
#define rs p<<1|1
struct node{
	int L,R;
}tmp[N],A[N];
int T,n,m,L,mxv,pos[N];
void init(){
	int d,v,a;
	for(int i=1;i<=n;i++){
		scanf("%d %d %d",&d,&v,&a);
		if(v<=mxv&&a<=0) tmp[i].L=-1,tmp[i].R=-1;
		if(v>mxv&&a>=0) tmp[i].L=d,tmp[i].R=L;
		if(v<=mxv&&a>0){
			int fpos=0;
			if((mxv*mxv-v*v)%(2*a)==0) fpos=d+(mxv*mxv-v*v)/(2*a)+1;
			else fpos=d+ceil((mxv*mxv-v*v)/(2*(double)a));
			if(fpos>L) tmp[i].L=tmp[i].R=-1;
			else tmp[i].L=fpos,tmp[i].R=L;
		}
		if(v>mxv&&a<0){
			int fpos=0;
			if((mxv*mxv-v*v)%(2*a)==0) fpos=d+(mxv*mxv-v*v)/(2*a)-1;
			else fpos=d+floor((mxv*mxv-v*v)/(2*(double)a));
			tmp[i].L=d,tmp[i].R=min(L,fpos);
		}
	}
	for(int i=1;i<=m;i++) scanf("%d",&pos[i]);
	sort(pos+1,pos+1+m);
	pos[m+1]=INF;
}
struct node2{
	int L,R;
	int val;
}tree[N<<2];
void up(int p){
	tree[p].val=tree[ls].val+tree[rs].val;
}
void build(int L,int R,int p){
	tree[p].L=L,tree[p].R=R;
	tree[p].val=0;
	if(L==R) return;
	int mid=(L+R)>>1;
	build(L,mid,ls);
	build(mid+1,R,rs);
}
void updata(int pos,int data,int p){
	if(tree[p].L==pos&&tree[p].R==pos){
		tree[p].val+=data;
		return;
	}
	int mid=(tree[p].L+tree[p].R)>>1;
	if(pos<=mid) updata(pos,data,ls);
	else if(pos>mid) updata(pos,data,rs);
	up(p);
}
int query(int L,int R,int p){
	if(tree[p].L>=L&&tree[p].R<=R) return tree[p].val;
	int mid=(tree[p].L+tree[p].R)>>1;
	if(R<=mid) return query(L,R,ls);
	else if(L>mid) return query(L,R,rs);
	else return query(L,R,ls)+query(L,R,rs);
}
bool cmp(node a,node b){
	return a.R<b.R;
}
int main(){
	cin>>T;
	while(T--){
		scanf("%d %d %d %d",&n,&m,&L,&mxv);
		init();
		int tot=0,ans1=0,ans2=0;
		build(0,L,1);
		for(int i=1;i<=m;i++) updata(pos[i],1,1);
		for(int i=1;i<=n;i++){
			if(tmp[i].L==-1||tmp[i].R==-1) continue;
			else if(query(tmp[i].L,tmp[i].R,1)>=1) A[++tot]=tmp[i];
		}
		sort(A+1,A+1+tot,cmp);
		build(0,L,1);
		ans1=tot;
		for(int i=1;i<=tot;i++){
			if(query(A[i].L,A[i].R,1)>=1) continue;
			int uitp=lower_bound(pos+1,pos+1+m+1,A[i].R)-pos;
			if(pos[uitp]>A[i].R) uitp--;
			updata(pos[uitp],1,1);
			ans2++;
		}
		printf("%d %d\n",ans1,m-ans2);
	}
	return 0;
}

2024/10/28 16:00
加载中...