求助90pts WA on #3
查看原帖
求助90pts WA on #3
532268
ayzhr435619楼主2024/11/9 20:59
#include<bits/stdc++.h>
#define int long long
#define RE register
#define AC 0
#define ctn continue
#define pii pair<int, int>
#define mkp make_pair
#define fst first
#define scd second
#define D(x) cout << #x << ": " << x << '\n';
#define De(x) cout << #x << ": " << x << ' ';
using namespace std;
inline int max(int a, int b){return a < b ? b : a;}
inline int min(int a, int b){return a < b ? a : b;}
inline int rd(){
	int x = 0;bool f = 0;char c = getchar();
	while(c > '9' || c < '0'){if(c == '-') f = 1;c = getchar();}
	while(c <= '9' && c >= '0'){x = (x << 3) + (x << 1) + (c - 48);c = getchar();}
	return f ? -x : x;
}
const int N = 1e6 + 7;
int T, n, m, L, V, sum1, sum2;
vector<pii> l_r;
vector<pii> lr;
int p[N];
bool vis[N];
signed main(){
//	freopen("detect.in", "r", stdin);
//	freopen("detect.out", "w", stdout);
	T = rd();
	while(T--){
//		cin >> n >> m >> L >> V;
		n = rd(), m = rd(), L = rd(), V = rd();
		sum1 = sum2 = 0;
//		D(V);
		l_r.clear();
		lr.clear();
		memset(vis, 0, sizeof(vis));
		for(RE int i = 1; i <= n; i = -~i){
//			cout << i << '\n';
			int d, v, a;
//			cin >> d >> v >> a;
			d = rd(), v = rd(), a = rd();
			if(a > 0){
				int LL = 0, RR = 1e7, ans = -1;
				while(LL <= RR){
					int mid = (LL + RR) >> 1;
					if(v * v + 2 * a * mid > V * V){
						RR = mid - 1;
						ans = mid;
					}
					else LL = mid + 1;
				}
				if(ans != -1){
//					D(ans);
					ans += d;
//					D(ans);
					if(ans <= L) l_r.push_back(mkp(ans, L));
				}
			}
			if(a == 0){
				if(v > V) l_r.push_back(mkp(d, L));
			}
			if(a < 0 && v > V){
				int LL = 0, RR = 1e12, ans = 1e7;
				while(LL <= RR){
					int mid = (LL + RR) >> 1;
					if(v * v + 2 * a * mid > V * V){
						LL = mid + 1;
						ans = mid;
					}
					else RR = mid - 1;
				}
//				if(ans != -1){
//					D(ans);
					ans += d;
//					D(ans);
					if(v > V) l_r.push_back(mkp(d, min(ans, L)));
//				}
			}
//			De(sum1);
//4*4*2*-4*1 = 7 < 3 * 3
		}
		for(RE int i = 1; i <= m; i = -~i){
//			cin >> p[i];
			p[i] = rd();
		}
		sort(p + 1, p + 1 + m);
//		for(RE int i = 1; i <= m; i = -~i){
//			D(p[i]);
//		}
		sort(l_r.begin(), l_r.end());
		int l = 0, r = 0;
//		for(RE int i = 0; i < l_r.size(); i = -~i){
//			De(l_r[i].fst) D(l_r[i].scd);
//		}
		for(RE int i = 1; i <= m; i = -~i){
			while(l_r[l].fst <= p[i] && l < l_r.size()){
				if(l_r[l].scd >= p[i]){
					vis[l] = 1;
				}
				l++;
			}
			if(l == l_r.size()) break;
		}
//		D(l_r.size());
		l = 0; r = INT_MAX;
		for(RE int i = 0; i < l_r.size(); i = -~i){
			if(vis[i]) sum1++, lr.push_back(l_r[i]);
		}
		for(RE int i = 1; i <= m; i = -~i){
			sum2++;
			if(i > 1){
				if(r >= p[i]){
					sum2--;
				}
				else r = INT_MAX;
			}
			while(lr[l].fst <= p[i] && l < lr.size()){
				if(lr[l].scd >= p[i]){
					vis[l] = 1;
					r = min(r, lr[l].scd);
				}
				l++;
			}
			if(l == lr.size()) break;
		}
//		last_r = 0;
//		for(RE int i = 0; i < l_r.size(); i = -~i){
//			De(l_r[i].fst);De(l_r[i].scd);
//			if(last_r < l_r[i].fst){
//				last_r = l_r[i].scd;
//				sum2++;
//			}
//			D(sum2);
//		}
		cout << sum1 << ' ' << m - sum2 << '\n';
	}
	return AC;
}

玄关

2024/11/9 20:59
加载中...