WA 民间70官方60求助

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5, M = 1e6 + 5;
const long double eps = 1e-5;

ll n, m, L, V; //车数量，检测器数量，道路长度，限速 
struct Car {
	ll d, v, a; //出发点，初速度，加速度 
} c[N];
ll p[N]; //传感器位置 

vector<pair<ll, ll> > v, v2;

long double dist(int id, long double t) { //返回车id行驶t时刻后所在位置 
	return c[id].d + c[id].v * t + 0.5 * c[id].a * t * t;
}
long double getV(int id, long double s) {
	return sqrt(c[id].v * c[id].v + 2 * c[id].a * s);
}
pair<ll, ll> chk(ll i) { //返回车id的超速区间，-1-1表示不超速 
	
	if (c[i].v <= V && c[i].a <= 0) {
		
		return make_pair(-1, -1);
	}
	if (c[i].v > V && c[i].a >= 0)
		return make_pair(c[i].d, L);
	if (c[i].v <= V) { 
		//若在ceil(dist(i, (V - c[i].v) / c[i].a))时是恰好等于V,要加一 
		long double t = 1. * (V - c[i].v) / c[i].a;
		
		ll pos = ceil(dist(i, t) + eps);
		if (pos > L) {
			return make_pair(-1, -1);
		}
		return make_pair(pos, L);
	}
	long double t = 1. * (c[i].v - V) / (-c[i].a);
	ll pos = floor(dist(i, t) - eps);
	if (pos < c[i].d)
		return make_pair(-1, -1);
	return make_pair(c[i].d, pos);
}

bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
	if (a.second != b.second)
		return a.second < b.second;
	return a.first < b.first;
}

int cnt[M] = {};
int T;

void slv() {
	scanf("%lld%lld%lld%lld", &n, &m, &L, &V);
	v.clear();
	v2.clear();
	for (int i = 1; i <= n; i++)  {
		scanf("%lld%lld%lld", &c[i].d, &c[i].v, &c[i].a);
		v.push_back(chk(i));
//		printf("[%d,%d]\n", chk(i).first, chk(i).second);
	}
	for (int i = 0; i <= L; i++)
		cnt[i] = 0;
	for (int i = 1; i <= m; i++) {
		scanf("%lld", &p[i]);
		cnt[p[i]]++;
	}
	for (int i = 1; i <= L; i++)
		cnt[i] += cnt[i - 1];
	
	int chaosu = 0;
	for (int i = 0; i < n; i++) {
		if (v[i].first == -1)
			continue;
		else if (cnt[v[i].second] - (v[i].first == 0 ? 0 : cnt[v[i].first - 1]) > 0) {
			
			chaosu++;
			v2.push_back(v[i]);
		}
	}
	
	
	
	int cnt_sensor = 0;
	sort(v2.begin(), v2.end(), cmp);
	for (int i = 0, lst = -1, j = 1; i < v2.size(); i++) { //lst标记目前最靠右的传感器
		if (lst >= v2[i].first)
			; //以前的已经有了 
		else {
			cnt_sensor++;
			//找到p中最接近i.second的传感器
			while (j < m && p[j + 1] <= v2[i].second)
				j++;
			lst = p[j];
		}
	}
	printf("%d %d\n", chaosu, m - cnt_sensor);
}

int main() {
	freopen("1.in", "r", stdin);
	freopen("1.out", "w", stdout);
	scanf("%d", &T);
	while (T--)
		slv();
	return 0;
}
/*
1
1 1 668183 893
444638 934 -310
444654
*/