40pts求调
查看原帖
40pts求调
1163927
F1NE楼主2024/11/11 19:46

rt,一出现a<0就爆了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxi=1e5+9;
ll V;
int T,
	N=0,M=0,L=0,
	d[maxi],v[maxi],a[maxi],
	p[maxi],loc,
	ans1,ans2;
bitset<maxi> over;
vector<pair<int,int> > itv,cal;
bool cmp(pair<int,int> a,pair<int,int> b){
	return a.second<b.second;
} 
inline int read(){
	int x=0;bool f=0;
	char ch=getchar();
	for(;ch<'0'||ch>'9';){
		if(ch=='-')f=1;ch=getchar();
	}
	for(;ch>='0'&&ch<='9';){
		x=x*10+ch-'0';ch=getchar();
	}
	return f?-x:x;
} 
namespace T2{
	inline void _clear(){
		for(int i=1;i<=N;i++){
			d[i]=v[i]=a[i]=0;
			
		}
		for(int i=1;i<=M;i++){
			p[i]=0;
		}
		itv.clear();cal.clear();
		over=0;ans1=ans2=0;
	}
	inline void getin(){
		N=read(),M=read(),L=read(),V=1ll*read();
//cerr<<"N="<<N<<",M="<<M<<",L="<<L<<",V="<<V<<'\n';
		for(int i=1;i<=N;i++){
			d[i]=read(),v[i]=read(),a[i]=read();
		}
		for(int i=1;i<=M;i++)p[i]=read();
	}
	inline void q1(){
		for(int i=1;i<=N;i++){
//cerr<<"i="<<i<<'\n'; 
			if(d[i]<=p[M]){
				if(a[i]==0){
//cerr<<(1ll*v[i]>V)<<'\n';
					if(1ll*v[i]>V)ans1++,over[i]=1;
				}
				else if(a[i]>0){
//cerr<<(1ll*2*a[i]*(p[M]-d[i])+1ll*v[i]*v[i])<<'\n';
					if(2ll*a[i]*(p[M]-d[i])+1ll*v[i]*v[i]>V*V)
					ans1++,over[i]=1;
				}
				else if(a[i]<0){
					loc=lower_bound(p+1,p+1+M,d[i])-p;

					if(2ll*a[i]*(p[loc]-d[i])+1ll*v[i]*v[i]>V*V)
					ans1++,over[i]=1;
				}
			}
		}
	}
	inline int bs1(int i){
		int l=loc,r=M,mid;
		for(;l!=r;){
			mid=(l+r)>>1;
			if(2ll*a[i]*(p[mid]-d[i])+1ll*v[i]*v[i]>V*V){
				r=mid;
			}else l=mid+1;
		}
		return l-1;
	}
	inline int bs2(int i){
		int l=loc-1,r=M+1,mid;
		for(;l<r;){
		mid=(l+r)/2;
//cerr<<"l="<<l<<",r="<<r<<",mid="<<mid<<'\n';
			
//cerr<<(2ll*a[i]*(p[mid]-d[i])+1ll*v[i]*v[i])<<' '
//<<V*V<<'\n';
			if(2ll*a[i]*(p[mid]-d[i])+1ll*v[i]*v[i]>V*V){
				l=mid+1;
			}else r=mid;
		}
//cerr<<(2ll*a[i]*(p[mid]-d[i])+1ll*v[i]*v[i])<<' '
//<<V*V<<'\n';
		return l;
	}
	inline void q2(){
		if(ans1!=0){
//cerr<<"started\n";
			for(int i=1;i<=N;i++){
				if(over[i]){
//cerr<<"ok\n";

				loc=lower_bound(p+1,p+1+M,d[i])-p;
//cerr<<"loc="<<loc<<'\n';
					if(a[i]==0){
						itv.push_back(make_pair(loc,M));	
					}
					if(a[i]>0){
						itv.push_back(make_pair(bs1(i),M));
					}
					if(a[i]<0){
						itv.push_back(make_pair(loc,bs2(i)));
					}
//
				}
			}
			sort(itv.begin(),itv.end(),cmp);
			int pos=0;
			for(auto i:itv){
//cerr<<"itv="<<i.first<<' '<<i.second<<'\n';
				if(i.first<=pos)continue;
				else{
					pos=i.second,ans2++;
				}
			} 
		}
	}
	inline void output(){
		printf("%d %d\n",ans1,M-ans2);
	}
	inline void solve(){
		_clear();
//cerr<<"cleared\n";
		getin();
//cerr<<"gotin\n";
		q1();
//for(int i=1;i<=N;i++)cerr<<"over["<<i<<"]="<<over[i]<<'\n';
//cerr<<"q1 ran\n";
		q2();
		output();
	}
	inline void init(){
		T=read();
//cerr<<"T="<<T<<'\n';
		for(int i=1;i<=T;i++)solve();
	}
}
int main(){
//	cerr<<read();
//	freopen("detect2.in","r",stdin);
//	freopen("out.out","w",stdout);
//	freopen("err.err","w",stderr);
	T2::init(); 
	return 0;
} 
2024/11/11 19:46
加载中...