Why TLE on #10
查看原帖
Why TLE on #10
556362
Unnamed114514楼主2022/3/12 23:01
#include<bits/stdc++.h>
#define mx(a,b) dp[a]>dp[b]?a:b
#define int long long
using namespace std;
const int maxn=1e5+5;
unordered_map<int,int> mp;
int n,a[maxn],tot,d,l[maxn],r[maxn],ans,dp[maxn],f[maxn],qwq,t,v[maxn*3];
struct Tree{
	#define ls k<<1
	#define rs k<<1|1
	#define Up(k) num[k]=mx(num[ls],num[rs])
	int num[maxn*12];
	void add(int k,int l,int r,int x,int v){
		if(l==r){
			num[k]=v;
			return;
		}
		int mid=l+r>>1;
		if(mid>=x)
			add(ls,l,mid,x,v);
		else
			add(rs,mid+1,r,x,v);
		Up(k);
	}
	int query(int k,int l,int r,int x,int y){
		if(x<=l&&r<=y)
			return num[k];
		int mid=l+r>>1,res=0;
		if(mid>=x)
			res=mx(res,query(ls,l,mid,x,y));
		if(mid<y)
			res=mx(res,query(rs,mid+1,r,x,y));
		return res;
	}
}x;
void print(int k){
	if(!k)
		return;
	print(f[k]);
	printf("%lld ",k);
}
inline int read(){
	int res=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+(ch^'0');
		ch=getchar();
	}
	return res;
}
signed main(){
	n=read(),d=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		v[++t]=a[i]-d;
		v[++t]=a[i];
		v[++t]=a[i]+d;
	}
	sort(v+1,v+t+1);
	for(int i=1;i<=t;++i)
		if(v[i]!=v[i-1])
			mp[v[i]]=++tot;
	for(int i=1;i<=n;++i)
		l[i]=mp[a[i]-d],r[i]=mp[a[i]+d],a[i]=mp[a[i]];
	for(int i=1;i<=n;++i){
		int k=mx(x.query(1,1,3*n,1,l[i]),x.query(1,1,3*n,r[i],tot));
		dp[i]=dp[k]+1;
		f[i]=k;	
		x.add(1,1,3*n,a[i],i);
		if(dp[i]>ans){
			ans=dp[i];
			qwq=i;
		}
	}
	printf("%lld\n",ans);
	print(qwq);
	return 0;
}
2022/3/12 23:01
加载中...