只有a>0和a=0的点错了求调(悬2关)
查看原帖
只有a>0和a=0的点错了求调(悬2关)
396033
zhengzixuan楼主2024/11/4 21:46
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int T, n, m, L, V, ans1, ans2;
vector<int> d, v, a, p;
pair<int, int> c[N];
void init(){
	ans1 = ans2 = 0;
	d.clear(), v.clear(), a.clear(), p.clear();
	for (int i = 0; i <= n; i++)
		c[i].first = c[i].second = 0;
}
void fi(int x){
	int dd = d[x], vv = v[x], aa = a[x];
	int l = 0, r = m - 1, mid, mm, mmm, ll, rr;
	while (l <= r){
		mid = (l + r) / 2;
		if (p[mid] >= dd)
			r = mid - 1;
		else
			l = mid + 1; 
	}
	mm = mid;
	for (int i = max(1, mid - 5); i <= min(m - 1, mid + 5); i++){
		if (p[i] >= dd && p[i - 1] < dd){
			mm = i;
			break;
		}
	}
	if (p[0] >= dd)
		mm = 0;
	if (aa == 0){
		if (vv > V){
			ans1++;
			c[x].first = mm, c[x].second = m - 1;
		}
		else{
			c[x].first = m, c[x].second = m;
		}
	}
	else if (aa > 0){
		long long vvv = 2ll * aa * (p[m - 1] - dd) + (long long)(vv * vv), VV = (long long)(V * V);
		if (vvv > VV){
			ans1++;
			c[x].second = m - 1;
			l = mm, r = m - 1, ll = l, rr = r;
			while (l <= r && l >= ll && r <= rr){
				mid = (l + r) / 2;
				vvv = (long long)(vv * vv) + 2ll * aa * (p[mid] - dd);
				if (vvv > VV)
					r = mid - 1;
				else
					l = mid + 1; 
			}
			mm = max(mm, mid), mid = mm;
			for (int i = max(ll, mid - 5); i <= min(rr, mid + 5); i++){
				if (p[i] >= dd){
					long long vvv1 = (long long)(vv * vv) + 2ll * aa * (p[i] - dd), vvv2 = (long long)(vv * vv) + 2ll * aa * (p[i + 1] - dd);
					if (vvv1 <= VV && vvv2 > VV){
						mm = i + 1;
					}
				}
			}
			c[x].first = mm;
		}
		else{
			c[x].first = m, c[x].second = m;
		}
	}
	else{
		long long VV = (long long)(V * V), vvv = (long long)(vv * vv) + 2ll * aa * (p[mm] - dd);
		if (vvv > VV){
			ans1++;
			c[x].first = mm;
			l = mm, r = m - 1, ll = l, rr = r;
			while (l <= r && l >= ll && r <= rr){
				mid = (l + r) / 2;
				vvv = (long long)(vv * vv) + 2ll * aa * (p[mid] - dd);
				if (vvv > VV)
					l = mid + 1;
				else
					r = mid - 1; 
			}
			mm = max(mm, mid), mid = mm;
			for (int i = max(ll, mid - 5); i <= min(rr, mid + 5); i++){
				if (p[i] >= dd){
					long long vvv1 = (long long)(vv * vv) + 2ll * aa * (p[i] - dd), vvv2 = (long long)(vv * vv) + 2ll * aa * (p[i + 1] - dd);
					if (vvv1 > VV && vvv2 <= VV){
						mm = i;
					}
				}
			}
			c[x].second = mm;
		}
		else{
			c[x].first = m, c[x].second = m;
		}
	}
} 
bool cmp(pair<int, int> x, pair<int, int> y){
	if (x.first != y.first)
		return x.first < y.first;
	return x.second > y.second;
}
int main(){
	// freopen("detect.in", "r", stdin);
	// freopen("detect.out", "w", stdout);
	scanf("%d", &T);
	while (T--){
		scanf("%d%d%d%d", &n, &m, &L, &V);
		for (int i = 0, x, y, z; i < n; i++){
			scanf("%d%d%d", &x, &y, &z);
			d.push_back(x), v.push_back(y), a.push_back(z);
		}
		for (int i = 0, x; i < m; i++){
			scanf("%d", &x);
			p.push_back(x);
		}
		for (int i = 0; i < n; i++)
			fi(i);
		sort(c, c + n, cmp);
//		for (int i = 0; i < m; i++)
//			cout << c[i].first << ' ' << c[i].second << endl;
		int nl = 0, nr = m;
		for (int i = 0; i < n; i++){
			nl = max(nl, c[i].first), nr = min(nr, c[i].second);
			if 	(nl > nr){
				ans2++;
				nl = c[i].first, nr = c[i].second;
			}	
		}
		if (nl == m && nr == m)
			ans2--;
		ans2 = m - ans2 - 1;
		printf("%d %d\n", ans1, ans2);
		init();
	}
	return 0;
} 
2024/11/4 21:46
加载中...