第一篇题解思路,求调!
查看原帖
第一篇题解思路,求调!
878013
_Supernova楼主2024/10/28 17:48
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <pii, ll> piii;
typedef long double ld;
const int N = 1e5 + 5;
int T, n, m, L, V;
int d[N], v[N], a[N], p[N];
int use[N];
struct range {
	int l, r;
	bool operator < (const range c) const {
		if (l == c.l) return r > c.r;
		else return l < c.l;
	}
} ra[N];
int main(void) {
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		memset(use, 0, sizeof use);
		cin >> n >> m >> L >> V;
		for (int i = 1; i <= n; ++i) {
			cin >> d[i] >> v[i] >> a[i];
		}
		for (int i = 1; i <= m; ++i) {
			cin >> p[i];
		}
		int numr = 0;
		for (int i = 1; i <= n; ++i) {
			if (v[i] <= V && a[i] <= 0) continue;
			if (a[i] > 0) {
				int upp;
				if (v[i] > V) upp = d[i] - 1;
				else upp = (V * V - v[i] * v[i]) / (2 * a[i]) + d[i];
				int l = 1, r = m, mid = 0, ans = 0;
				while (l <= r) {
					mid = (l + r) >> 1;
					if (p[mid] > upp) {
						r = mid - 1;
						ans = mid;
					}
					else {
						l = mid + 1;
					}
				}
				if (!ans) continue;
				ra[++numr] = (range){ans, m};
			}
			else {
				int pos = 0, l = 1, r = m, mid = 0;
				while (l <= r) {
					mid = (l + r) >> 1;
					if (p[mid] >= d[i]) {
						r = mid - 1;
						pos = mid;
					}
					else {
						l = mid + 1;
					}
				}
				if (!pos) continue;
				l = pos, r = m, mid = 0;
				int ans = 0;
				while (l <= r) {
					mid = (l + r) >> 1;
					long double v0 = sqrt(v[i] * v[i] + 2 * a[i] * (p[mid] - d[i]));
					if (v0 > V) {
						r = mid - 1;
						ans = mid;
					}
					else {
						l = mid + 1;
					}
				}
				if (!ans || ans < pos) continue;
				ra[++numr] = (range){pos, ans};
			}
		}
		sort(ra + 1, ra + numr + 1);
		int minr = 0x3f3f3f3f;
		for (int i = numr; i >= 1; --i) {
			if (minr <= ra[i].r) use[i] = 1;
			minr = min(minr, ra[i].r);
		}
		int las = 0, ans = 0;
		for (int i = 1; i <= numr; ++i) {
			if (use[i] == 1) continue;
			if (las < ra[i].l) {
				las = ra[i].r;
				++ans;
			}
		}
		ans = m - ans;
		cout << numr << ' ' << ans << '\n';
	}
	return 0;
}
2024/10/28 17:48
加载中...