rt,TLE了,求各位大佬帮忙看看时间复杂度有没有问题
  • 板块学术版
  • 楼主daduoli
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/1/28 21:25
  • 上次更新2023/10/24 02:46:30
查看原帖
rt,TLE了,求各位大佬帮忙看看时间复杂度有没有问题
107154
daduoli楼主2023/1/28 21:25
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)

using namespace std;
const int MAXN=2e5+10,inf=2147483647;
int n,m,cnt;
struct ddl {
	int a,b;
}a[MAXN];
int lsh[MAXN];
vector<int>b[MAXN];

struct daduoli {
	int size,l;
}tree[MAXN*4];
void push_up(int node) {
	tree[node].l=min(tree[(node<<1)].l,tree[(node<<1|1)].l);
}
void update(int node,int l,int r,int x,int y) {
	if(l>x||r<x) return ;
	if(l==r) {
		tree[node].size+=y;
		if(tree[node].size) tree[node].l=l;
		else tree[node].l=inf;
		return ;
	}
	int mid=((l+r)>>1);
	update((node<<1),l,mid,x,y);
	update((node<<1|1),mid+1,r,x,y);
	push_up(node);
}
int query(int node,int l,int r,int x,int y) {
	if(l>y||r<x) return inf;
	if(l>=x&&r<=y) return tree[node].l;
	int mid=((l+r)>>1);
	return min(query((node<<1),l,mid,x,y),query((node<<1|1),mid+1,r,x,y));
}

int dis[MAXN];
bool vis[MAXN];
priority_queue<pair<pair<int,int> ,pair<int,int> >,vector<pair<pair<int,int> ,pair<int,int> > >,greater<pair<pair<int,int> ,pair<int,int> > > >q;
void work() {
	memset(dis,127,sizeof(dis));
	dis[1]=0;
	q.push(make_pair(make_pair(0,1),make_pair(a[1].b,a[1].b)));
	while(!q.empty()) {
		int distance=q.top().first.first,u=q.top().first.second;
		int L=q.top().second.first,R=q.top().second.second;
		q.pop();
		
		if(vis[u]) continue;
		vis[u]=1;
		
		
		dis[u]=distance;
		if(u!=1) {
			update(1,1,cnt,a[u].b,-1);
			b[a[u].b].pop_back();
		}
		int mid=lower_bound(lsh+1,lsh+1+cnt,m-a[u].a)-lsh-1;
		int mm1=query(1,1,cnt,1,mid),mm2=query(1,1,cnt,mid+1,cnt);
		if(mm1!=inf) {
			int mb1=b[mm1].back();
			q.push(make_pair(make_pair(distance+a[u].a+lsh[a[mb1].b]  ,mb1),make_pair(1,mid)));
		}
		if(mm2!=inf) {
			int mb2=b[mm2].back();
			q.push(make_pair(make_pair(distance+a[u].a+lsh[a[mb2].b]-m,mb2),make_pair(mid+1,cnt)));
		}
		if(u==1) continue;
		int mm3=query(1,1,cnt,L,R);
		if(mm3!=inf) {
			int mb3=b[mm3].back();
			q.push(make_pair(make_pair(distance+lsh[mm3]-lsh[a[u].b],mb3),make_pair(L,R)));
		}
	}
}
int main() {
	cin>>n>>m;
	for(int i=1;i<MAXN*4;++i) tree[i].l=inf;
	for(int i=1;i<=n;++i) scanf("%d",&a[i].a);
	for(int i=1;i<=n;++i) scanf("%d",&a[i].b),lsh[i]=a[i].b;
	sort(lsh+1,lsh+1+n);
	cnt=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1;i<=n;++i) {
		a[i].b=lower_bound(lsh+1,lsh+1+cnt,a[i].b)-lsh;
		if(i>1) b[a[i].b].push_back(i),update(1,1,cnt,a[i].b,1);
	}
	work();
	cout<<dis[n];
	return 0;
} 
2023/1/28 21:25
加载中...