右端点40pts+TLE求条
查看原帖
右端点40pts+TLE求条
681558
Weizhuo_Zhao楼主2024/11/18 13:17
#include <bits/stdc++.h>
#define MAX_N 100005
using namespace std;
int n, m, L, V;

struct car {
	int d, v, a_;
};
car a[MAX_N];
int p[MAX_N];
vector<pair<int, double> >wzy;

void read() {
	cin >> n >> m >> L >> V;
	for (int i = 1; i <= n; i++)
		cin >> a[i].d >> a[i].v >> a[i].a_;
	for (int i = 1; i <= m; i++)
		cin >> p[i];
}
int max_s = INT_MIN;

int find() {
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].d > p[m]) //超过检测不到
			continue;
		if (!a[i].a_) { //a=0
			if (a[i].v > V) {
				ans++;
				max_s = max(max_s, a[i].d);
			}
			continue;
		}
		if (a[i].a_ > 0) {//a>0
			if (a[i].v > V) {
				ans++;
				max_s = max(max_s, a[i].d);
				continue;
			}
			double s = (V * V - a[i].v * a[i].v) * 1.0 / (2 * a[i].a_);
			s += a[i].d;
			if (s >= p[m])
				continue;
			max_s = max(max_s, int(s) + 1);
			ans++;
			continue;
		}
		//a<0
		if (a[i].v <= V)
			continue;
		double s = (V * V - a[i].v * a[i].v) * 1.0 / (2 * a[i].a_); //v==V->s
		s += a[i].d;
		int l = 1, r = m;
		int num = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (p[mid] <= a[i].d) {
				l = mid + 1;
				continue;
			}
			if (p[mid] > s) {
				r = mid - 1;
				continue;
			}
			wzy.push_back(make_pair(a[i].d, s));
			ans++;
			break;
		}
	}
	return ans;
}

bool cmp(pair<int, double>x, pair<int, double>y) {
	return x.second > y.second;
}

int qwq() {
	if (wzy.empty())
		return 1;
	sort(wzy.begin(), wzy.end(), cmp);
	double j = -1;
	int len = wzy.size(), ans = 0, rightest = 0;
	bool flag = false; //false->第一个
	for (int i = 0; i < len; i++) {
//		cout << wzy[i].first << ' ' << wzy[i].second << '\n';
		if (j >= wzy[i].first && j <= wzy[i].second)
			continue;
		int l = 1, r = n;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (p[mid] < wzy[i].first) {
				l = mid + 1;
				continue;
			}
			r = mid - 1;
			j = mid;
		}
		ans++;//此内必有检测点
		//j = wzy[i].second;
		if (!flag) {
			rightest = j;
			flag = true;
		}
	}
	if (rightest < max_s)
		ans++;
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		read();
		int x = find();
		cout << x << ' ';
		if (!x) {
			cout << m << '\n';
			continue;
		}
		if (x && m == 1) {
			cout << 0 << '\n';
			continue;
		}
		cout << m - qwq() << '\n';
	}
}
2024/11/18 13:17
加载中...