80pts,wa了两个点,求调,玄关
查看原帖
80pts,wa了两个点,求调,玄关
755114
CD43楼主2025/8/2 18:54
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,m;
double d[100005],v[100005],a[100005];
double p[100005];
struct node{
	int l , r;
	bool t;
}q[100005];
//int search1(double x)
//{
//	int l = 1 , r = m;
//	while(l<r)
//	{
//		int mid = (l + r) / 2;
//		if(x <= p[mid])
//		{
//			r = mid;
//		}
//		else
//		{
//			l = mid + 1;
//		}
//	}
//	return l;
//}
//int search2(double x)
//{
//	int l = 1 , r = m;
//	while(l<r)
//	{
//		int mid = (l + r) / 2;
//		if(x <= p[mid])
//		{
//			r = mid;
//		}
//		else
//		{
//			l = mid + 1;
//		}
//	}
//	return l - 1;
//}
int search1(double x) {
    int l = 1, r = m, ans = m + 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (p[mid] >= x) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

int search2(double x) {
    int l = 1, r = m, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (p[mid] <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}
bool cmp(node xx, node yy)
{
    if (xx.t != yy.t)return xx.t > yy.t;
    if (xx.r != yy.r)return xx.r < yy.r;
    return xx.l < yy.l;
}
signed main()
{
//	freopen("ce.txt","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		double L,V;
		int tot=0;
		cin>>n>>m>>L>>V;
		memset(d,0,sizeof(d));
		memset(v,0,sizeof(v));
		memset(a,0,sizeof(a));
		memset(p,0,sizeof(p));
		memset(q,0,sizeof(q));
		V+=0.000001;
		for(int i=1;i<=n;i++)
		{
			cin>>d[i]>>v[i]>>a[i];
		}
		for(int i=1;i<=m;i++)
		{
			cin>>p[i];
		}
		for(int i=1;i<=n;i++)
		{
			if(a[i] == 0)
			{
				if(v[i] >= V)
				{
					q[i].t = 1;
					q[i].l = search1(d[i]);
					q[i].r = m;
				}
				
//				if(q[i].t)cout<<i<<':'<<v[i]<<' '<<q[i].l<<' '<<q[i].r<<endl;
				tot += q[i].t;
			}
			if(a[i] > 0)
			{
				double s = (V * V - v[i] * v[i]) / (2 * a[i]);
				s = max(s + d[i] , d[i]);
				q[i].l = search1(s);
				q[i].r = m;
				
				if(s <= p[m] && q[i].l <= m)q[i].t = 1;
				
//				if(q[i].t)cout<<i<<':'<<s<<' '<<q[i].l<<' '<<q[i].r<<endl;
				tot += q[i].t;
			}
			if(a[i] < 0)
			{
				double s = (V * V - v[i] * v[i]) / (2 * a[i]);
				q[i].l = search1(d[i]);
				q[i].r = search2(d[i] + s);
				if(d[i] + s >= p[m])q[i].r = m;
				if(q[i].r >= q[i].l && v[i] >= V && q[i].r <= m)q[i].t = 1;
				
//				if(q[i].t)cout<<i<<':'<<d[i] + s<<' '<<q[i].l<<' '<<q[i].r<<endl;
				tot += q[i].t;	
			}
		}
		sort(q + 1 , q + 1 + n , cmp);
		int ans = 1,r = q[1].r;
		for(int i = 1 ; i <= tot ; i++)
		{
			if(q[i].l > r)
			{
				ans++;
				r = q[i].r;
			}
		}
		cout<<tot<<' '<<m - ans<<endl;
		
	}
	return 0;
}
/*
1
10 10 145322 772
 10139 897 -47
 86524 947 -2
 51251 982 -2
 12573 962 -2
 14068 919 -163
 10944 994 -6
 35650 999 -9
 3804 977 -1
 1149 905 -2
 43935 932 -2
 10519  11805  14747  28890  37732  45509  55779  80531  108392  126659

*/

评测记录 : https://www.luogu.com.cn/record/228433117

2025/8/2 18:54
加载中...