70pts求调
查看原帖
70pts求调
743546
huangyuze01楼主2024/10/29 17:42
#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i = a; i <= b; i++)
#define F_(i,a,b) for(int i = a; i >= b; i--)
#define pii pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5+10,M = 1e3+10;
const ll mod = 998244353;
// huangyuze
int t;
int n,m,L,V,p[N];
int ans1,ans2;
bool cs[N];//标记哪些车超速 
set<pii> st;//区间(first为右端点,second为左端点) 
struct CAR{
	int d,v,a;
} car[N];
void init(){
	memset(cs,0,sizeof(cs));
	ans1=ans2=0;
	st.clear();
}
void solve1(){
	F(i,1,n){
		int d=car[i].d,v=car[i].v,a=car[i].a;
		if (a==0){
			if (v<=V) continue;
			if (p[m]<d) continue;
			cs[i] = 1;
			st.insert({L,d});
		} else if (a>0){
			int pos;
			if (v>V) pos=d;
			else pos = (V*V-v*v)/(2*a)+d+1;
			if (p[m]<pos) continue;
			cs[i] = 1;
			st.insert({L,pos});
		} else {
			if (v<=V) continue;
			int pos = (V*V-v*v+2*a-1)/(2*a)+d-1;
			int p2 = upper_bound(p+1,p+m+1,pos)-p-1;
			if (p[p2]<d) continue;
			cs[i] = 1;
			st.insert({pos,d});
		}
	}
}
void solve2(){
    //最小点覆盖 
	int lst=-1;
	for (auto x:st){
		int fr=x.second,se=x.first;
		if (fr>lst){
			ans2++;
			int pos = upper_bound(p+1,p+m+1,se)-p-1;
			lst = p[pos];
		}
	}
}
void work(){
	init();
	scanf("%d%d%d%d",&n,&m,&L,&V);
	F(i,1,n) scanf("%d%d%d",&car[i].d,&car[i].v,&car[i].a);
	F(i,1,m) scanf("%d",p+i);
	solve1();
	F(i,1,n) if (cs[i]) ans1++;
	solve2();
	printf("%d %d\n",ans1,m-ans2);
}
int main(){
	scanf("%d",&t);
	while (t--) work();
	return 0;
} 

评测记录

2024/10/29 17:42
加载中...