RE TLE 0 ptc 求调试
查看原帖
RE TLE 0 ptc 求调试
1010570
违规用户名1010570楼主2024/11/13 20:17
#include<bits/stdc++.h>
using namespace std;
int T;
int n,m,l,vv;
int d[100005],v[100005],a[100005],p[100005];
struct st{
	int le,ri;
};
vector<st> len;
bool cmp(st x,st y){
	x.ri<y.ri;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m>>l>>vv;
		for(int i=1;i<=n;i++){
			cin>>d[i]>>v[i]>>a[i];
		}
		for(int i=1;i<=m;i++){
			cin>>p[i];
		}
		len.clear();
		for(int i=1;i<=n;i++){
			if(a[i]==0){
				if(v[i]<=vv){
					continue;
				}
				len.push_back({d[i],l});
			}
			else if(a[i]>0){
				if(v[i]>vv){
					len.push_back({d[i],l});
				}
				else{
					int s=(vv*vv-v[i]*v[i])/(2*a[i])+1;
					if(d[i]+s<=l){
						len.push_back({d[i]+s,l});
					}
				}
			}
			else if(a[i]<0){
				if(v[i]<vv){
					continue;
				}
				int s=(vv*vv-v[i]*v[i])/(2*a[i]);
				if((vv*vv-v[i]*v[i])%(2*a[i])==0){
					s--;
				}
				if(s<0){
					s=0;
				}
				len.push_back({d[i],min(l,d[i]+s)});
			}
		}
		sort(len.begin(),len.end(),cmp);
		int pos=-1,last=-1,ans1=0,ans2=0;
		for(int i=0;i<len.size();i++){
			if(len[i].le<=last){
				ans1++;
				continue;
			}
			while(pos<=m&&len[i].le<=p[pos]&&p[pos]<=len[i].ri){
				last=p[pos];
				pos++,ans1++,ans2++;
			}
		}
		cout<<ans1<<" "<<m-ans2<<"\n";
	}
}
2024/11/13 20:17
加载中...