80pts WA on #8 #10 求调
查看原帖
80pts WA on #8 #10 求调
685964
shuqiang楼主2024/11/30 20:57

应该是 ai<0a_i<0 挂了。

#include<iostream>
#include<algorithm> 

using namespace std;

const int N = 1e5 + 10;
int t, n, m, L, V, d[N], v[N], a[N], p[N], ans1, ans2;

struct pii{
	int l, r;
	
	bool operator < (const pii & o) const{
		return r < o.r;
	}
} q[N];

int main(){
	cin >> t;
	while(t--){
		cin >> n >> m >> L >> V;
		ans1 = ans2 = 0;
		for(int i = 0; i < n; i++){
			cin >> d[i] >> v[i] >> a[i];
		}
		for(int i = 0; i < m; i++){
			cin >> p[i];
		}
		for(int i = 0; i < n; i++){
			if(a[i] == 0){
				if(d[i] <= p[m-1] && v[i] > V){
					int posl = lower_bound(p, p + m, d[i]) - p;
					if(posl >= m) posl--;
					q[i].l = posl;
					q[i].r = m-1;
					ans1++;
				}
				else q[i].l = q[i].r = -1;
			}
			else if(a[i] > 0){
				if(d[i] + ((V * V - v[i] * v[i]) / a[i] / 2 + 1) <= p[m-1] && d[i] <= p[m-1]){
					int posl = lower_bound(p, p + m, d[i]) - p;
					if(posl >= m) posl--;
					q[i].l = posl;
					q[i].r = m-1;
					ans1++;
				}
				else q[i].l = q[i].r = -1;
			}
			else{
				if(v[i] < V){
					q[i].l = q[i].r = -1;
				}
				else{
					int numl = d[i];
					int numr = d[i] + ((V * V - v[i] * v[i] - 1) / a[i] / 2);
					int posl = lower_bound(p, p + m, numl) - p;
					int posr = lower_bound(p, p + m, numr) - p;
					if(posl >= m) posl--;
					if(posr >= m) posr--;
					if((numl == p[posl] || numr == p[posr] || (numr >= p[posr] && numr != m-1) || posr - posl >= 1) && posl <= posr){
						ans1++;
						q[i].l = posl;
						if(numr >= p[m-1]) q[i].r = posr;
						else q[i].r = max(posr-(numr < p[posr]), posl);
					}
					else q[i].l = q[i].r = -1;
				}
			}
		}
		sort(q, q + n);
		int mxr = -1;
		for(int i = 0; i < n; i++){
			if(q[i].r == -1) continue;
			bool fg = 0;
			if(q[i].l > mxr){
				mxr = q[i].r;
				ans2++;
			}
		}
		cout << ans1 << ' ' << m-ans2 << '\n';
	}
	return 0;
}

2024/11/30 20:57
加载中...