50分TLE了,怎么在原代码基础上减小复杂度啊
查看原帖
50分TLE了,怎么在原代码基础上减小复杂度啊
754006
mobaiawa楼主2024/11/3 14:58
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10,M=2e6+10;
ll n,m,L,V;
ll read(){
	ll res=0;bool op=1;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')op^=1;ch=getchar();}
	while('0'<=ch&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
	return op?res:-res;
}
void write(ll x){
	if(x<0){x=-x;putchar('-');}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct tree{
	int w[M];
	void clear(){
		memset(w,0,sizeof w);
	}
	int lb(int x){return x&-x;}
	void add(int x){
		for(;x<=L;x+=lb(x))w[x]++;
	}
	int ask(int x){
		if(x<0)return 0;
		int res=0;
		for(;x;x-=lb(x))res+=w[x];
		return res;
	}
	void print(int siz){
		puts("-----------------");
		for(int i=1;i<=siz;i++)printf("%3d ",i);
		cout<<"\n";
		for(int i=1;i<=siz;i++)printf("%3d ",w[i]);		
		puts("-----------------");
	}
}tr,v;
struct node{
	ll first,second;
	bool operator<(const node &y)const{
		if(second==y.second)return first<y.first;
		return second<y.second;
	}
};
node makepair(ll x,ll y){
	node res;
	res.first=x;res.second=y;
	return res;
}
node get(ll d,ll v,ll a,ll L,ll V){//st,ed
	if(a==0){
		if(v>V)return makepair(d,L);//匀速 
		else return makepair(-1,-1);
	}
	else if(a>0){
		if(v>V)return makepair(d,L);
		if(V*V>=v*v+2*a*(L-d))return makepair(-1,-1);
		ll loc=d+ceil(1.0*(V*V-v*v)/(2*a));//匀加速 
		return makepair(loc,L);
	}
	else {
		if(v<=V)return makepair(-1,-1);
		else {
			ll loc=d+floor(1.0*(V*V-v*v)/(2*a));//匀减速 
			return makepair(d,min(L,loc));
		}
	}
}
node dat[N];

void slove(){
	tr.clear();
	v=tr;//初始化 
	n=read(),m=read(),L=read(),V=read();
	for(int i=1;i<=n;i++){
		ll d=read(),v=read(),a=read();
		node x=get(d,v,a,L,V);//查找超速区间 
		dat[i]=x;//存下超速区间 
	}
	for(int i=1;i<=m;i++){
		int p=read();
		tr.add(p);//这个点有一个测速仪 
	}
	ll ans1=0,ans2=0;
	sort(dat+1,dat+1+n);
	for(int i=1;i<=n;i++){
		if(dat[i].first==-1)continue;//没超速 
		ll st=dat[i].first,ed=dat[i].second;//超速区间 
		int l=tr.ask(st-1),r=tr.ask(ed);//测速仪编号 
		if(l==r)continue;//测速仪全开也测不到超速 
		ans1++; 
//			cout<<l<<" "<<r<<" "<<st<<" "<<ed<<"<\n";
		if(!(v.ask(r)-v.ask(l))){//查找区间中是否有开启的测速仪 
			ans2++;//要多开一个 
			v.add(r);//选右端点 
		}
	}
	write(ans1); 
	putchar(' ');
	write(m-ans2);//全部的测速仪减去开了的就是没开的 
	putchar('\n');
}
int main(){
//	freopen("detect2.in","r",stdin);
//	freopen("detect.out","w",stdout);
	int T=read();
	while(T--)slove();
	return 0;
} 
2024/11/3 14:58
加载中...