80分 1,2,wa 求调
查看原帖
80分 1,2,wa 求调
777059
Lyu_Lintse楼主2024/11/2 21:55
#include<bits/stdc++.h>
using namespace std;
int n,m,l,V,T;
struct ccf
{
	int d,v,a,b,e;
} c[100050];
bool cmp(ccf c1,ccf c2)
{
	if(c1.b!=c2.b)
	{
		return c1.b<c2.b;
	}
	return c1.e>c2.e;
}
int ip,cf[100050],qzh[100050],lb[100050],ub[100050],cp;
bool pded[100050];
vector<int> p;
int main()
{
    cin>>T;
    while(T--)
    {
        p.erase(p.begin(),p.end());
        cin>>n>>m>>l>>V;
        for(int i=0;i<n;i++)
        {
            cin>>c[i].d>>c[i].v>>c[i].a;
            if(c[i].v<=V and c[i].a<=0)
            {
                i--;
                n--;
            }
            else if(c[i].v>V and c[i].a>=0)
            {
                c[i].b=c[i].d;
                c[i].e=l;
            }
            else if(c[i].v==V and c[i].a>0)
            {
                c[i].b=c[i].d+1;
                c[i].e=l;
            }
            else if(c[i].v<V)
            {
                c[i].b=c[i].d+floor((double)(V*V-c[i].v*c[i].v)/(2*c[i].a)+1);
                c[i].e=l;
                if(c[i].b>l)
                {
                    i--,n--;
                }
            }
            else
            {
                c[i].b=c[i].d;
                c[i].e=min(c[i].d+ceil((double)(V*V-c[i].v*c[i].v)/(2*c[i].a)-1),(double)l);
            }
        }
        for(int i=0;i<m;i++)
        {
            cin>>ip;
            p.push_back(ip);
        }
        sort(p.begin(),p.end());
        int ans1=0,j=0,ans2=0;
        for(int i=0;i<n;i++)
        {
            if(lower_bound(p.begin(),p.end(),c[i].b)-p.begin()==upper_bound(p.begin(),p.end(),c[i].e)-p.begin())
            {
                ans1++;
            }
            else
            {
                c[j++]=c[i];
            }
        }
        cout<<n-ans1<<' ';
        n-=ans1;
        sort(c,c+n,cmp);
        reverse(c,c+n);
        j=0;
        c[j++]=c[0];
        for(int i=1;i<n;i++)
        {
        	if(c[i].e<c[j-1].e)
        	{
        		c[j++]=c[i];
			}
		}
		reverse(c,c+j);
		int nowr=-1;
//		for(int i=0;i<j;i++)
//		{
//			cout<<c[i].b<<' '<<c[i].e<<endl;
//		}
		for(int i=0;i<j;i++)
		{
			if(!(c[i].b<=nowr and nowr<=c[i].e))
			{
				vector<int>::iterator it=upper_bound(p.begin(),p.end(),c[i].e); 
				it--;
				nowr=*it;
//				cout<<nowr<<' '; 
				ans2++;
			}
		}
		if(n-ans1==0)
		{
			cout<<m<<endl;
		} 
		else
		{
		 	cout<<m-ans2<<endl;
		}
		
    }
    return 0;
}
2024/11/2 21:55
加载中...