90分WA最后一点求调
查看原帖
90分WA最后一点求调
1017253
xuan_never楼主2024/10/26 23:14

RT,本蒻的赛时代码,不会是精度炸了吧。。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
int T, n, m, L, V;
ll d[100050], v[100050], a[100050], p[100050];
pii lis[100050];
int an1, an2;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	for (cin >> T; T--;) {
		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];
		an1 = 0;
		for (int i = 1, t, l; i <= n; ++i) {
			l = an1;
			if (a[i] == 0 && v[i] > V && p[m] >= d[i]) {
				lis[i].fi = lower_bound(p + 1, p + 1 + m, d[i]) - p,
				lis[i].se = m;
				++an1;
			} else if (a[i] > 0 && p[m] >= d[i] && v[i] * v[i] + 2 * a[i] * (p[m] - d[i]) > V * V) {
				lis[i].fi = lower_bound(p + 1, p + 1 + m, d[i] + ll((V * V - v[i] * v[i]) * 0.5 / a[i] + 1)) - p,
				lis[i].se = m;
				++an1;
			} else if (a[i] < 0 && v[i] > V && p[m] >= d[i]) {
				t = lower_bound(p + 1, p + 1 + m, d[i]) - p;
				if (v[i] * v[i] + 2 * a[i] * (p[t] - d[i]) > V * V) {
				lis[i].fi = t,
				lis[i].se = lower_bound(p + 1, p + 1 + m, d[i] + (ll)ceil((V * V - v[i] * v[i]) * 0.5 / a[i])) - p - 1;
				++an1;
				}
			}
			if (l == an1) lis[i] = {1e9, 1e9};
		}
		cout << an1 << ' ';
		if (!an1) {
			cout << m << '\n';
			continue;
		}
		an2 = 1;
		sort(lis + 1, lis + 1 + n, [](pii x, pii y) {
			if (x.se == y.se) return x.fi < y.fi;
			return x.se < y.se;
		});
		for (int i = 2, la = 1; i <= n; ++i) {
			if (lis[i].fi == 1e9 || lis[i].se == 1e9) break;
			if (lis[i].fi > lis[la].se) ++an2, la = i;
		}
		cout << m - an2 << '\n';
	}
	return 0;
}
2024/10/26 23:14
加载中...