Submission #26951256

---

Source Code Expand

#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define WT int TT=read();while(TT--) 
#define NO puts("NO");
#define YES puts("YES");
using namespace std;

inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

const int inf=1e9;
const int M=5e5+10;
int n,k,a[M],b[M],p[M],ans[M],vis[M];
priority_queue<int>q;

struct segment_tree
{
	struct tree
	{
		int tl,tr,val;
	}t[M<<2];
	#define l(x) t[(x)].tl
	#define r(x) t[(x)].tr
	#define val(x) t[(x)].val
	#define lson k<<1
	#define rson k<<1|1
	void pushup(int k){val(k)=max(val(lson),val(rson));}
	void build(int k,int l,int r)
	{
		l(k)=l,r(k)=r;
		if (l==r){val(k)=a[l];return;}
		int Mid=(l+r)>>1;
		build(lson,l,Mid),build(rson,Mid+1,r);
		pushup(k);
	}
	void update(int k,int l)
	{
		if (l(k)==l&&r(k)==l){val(k)=-inf;return;}
		if (l(k)>l||r(k)<l)return;
		update(lson,l),update(rson,l);
		pushup(k);
	}
	int query(int k,int l,int r)
	{
		if (l(k)>=l&&r(k)<=r)return val(k);
		if (l(k)>r||r(k)<l)return -inf;
		return max(query(lson,l,r),query(rson,l,r));
	}
}T;

int check(int x){return a[x]==T.query(1,x-k+1,x+k-1);}

signed main()
{
	n=read(),k=read();
	for (int i=1;i<=n;i++)a[i]=read(),b[a[i]]=i;
	T.build(1,1,n);
	for (int i=1;i<=n;i++)
		if (check(i))q.push(i),vis[i]=1;//,cout<<i<<' ';
	for (int i=n;i>=1;i--)
	{
		int x=q.top();q.pop();p[i]=x;
		T.update(1,x);
		int x1=T.query(1,x-k+1,x-1);
		if (x1!=-inf&&check(b[x1]))q.push(b[x1]),vis[b[x1]]=1;
		x1=T.query(1,x+1,x+k-1);
		if (x1!=-inf&&check(b[x1]))q.push(b[x1]),vis[b[x1]]=1;
	}
	for (int i=1;i<=n;i++)ans[p[i]]=i;
	for (int i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
}

Submission Info

Judge Result