有没有大佬帮忙调下提高T3代码
查看原帖
有没有大佬帮忙调下提高T3代码
1053325
ruirui1楼主2024/10/29 16:42
#include <bits/stdc++.h>
using namespace std;
struct node1{
	long long di,vi,ai;
}b[200005];
struct node{
	long long li,ri;
}a[200005];
long long t,m,n,l,v,kkk,ll,k[200005],len,ans1,ans2,vis[200005];
int cmp(node x,node y){
	return x.ri<y.ri;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>t;
	while(t--){
		cin>>n>>m>>l>>v;
		len=0;
		ans1=0,ans2=0;
		for(int i=1;i<=n;i++){
			cin>>b[i].di>>b[i].vi>>b[i].ai;
		}
		for(int i=1;i<=m;i++){
			cin>>k[i];
		}
		for(int i=1;i<=n;i++){
			if(b[i].vi>v){
				if(b[i].ai>=0){
					a[i].li=b[i].di;
					a[i].ri=l;
				} else{
					kkk=(v*v-b[i].vi*b[i].vi)/(2*b[i].ai);
					if((v*v-b[i].vi*b[i].vi)%(2*b[i].ai)==0) kkk--;
					a[i].li=b[i].di;
					a[i].ri=b[i].di+kkk;
					if(a[i].ri>l) a[i].ri=l;
				}
			} else{
				if(b[i].ai<=0){
					a[i].li=l+1;
					a[i].ri=l+1;
				} else{
					kkk=(v*v-b[i].vi*b[i].vi)/(2*b[i].ai);
					if((v*v-b[i].vi*b[i].vi)%(2*b[i].ai)==0) kkk++;
					a[i].li=b[i].di+kkk;
					a[i].ri=l;
					if(a[i].li>l) a[i].ri=l+1;
				}
			}
		}
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;i++){
			if(a[i].li>l) continue;
			ll=upper_bound(vis+1,vis+len+1,a[i].ri)-vis-1;
			if(vis[ll]>=a[i].li&&vis[ll]<=a[i].ri){
				ans1++;
				continue;
			} else{
				ll=upper_bound(k+1,k+m+1,a[i].ri)-k-1;
				if(k[ll]>=a[i].li&&k[ll]<=a[i].ri){
					ans1++;
					ans2++;
					vis[++len]=k[ll];
				}
			}
		}
		cout<<ans1<<" "<<m-ans2<<"\n";
	}
	return 0;
}
2024/10/29 16:42
加载中...