Submission #3051402

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lf (x<<1)
#define rg (lf|1)
#define mem(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for (i=j;i<=k;i++)
using namespace std;
const int N=5e5+5,INF=1e9;
int n,k,wh,mode,i,a[N],p[N],deg[N],out[N];
int Min[N*4],cs[N*4],dec[N*4];
int sum[N];
template <typename T> void read(T &ret)
{
	char ch; ret=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';
}
int lowbit(int x) {return x&(-x);}
void add(int x) {
	while (x<=n) { sum[x]++; x+=lowbit(x); }
}
int query(int x) {
	if (x<1) return 0;
	if (x>n) x=n;
	int ret=0; while (x>0) {ret+=sum[x]; x-=lowbit(x);}
	return ret;
}
void merge(int x)
{
	Min[x]=min(Min[lf],Min[rg]);
	cs[x]=min(cs[lf],cs[rg]);
}
void build(int x,int l,int r)
{
	if (l==r)
	{
		if (!deg[l]) { Min[x]=INF; cs[x]=l; }
		else Min[x]=deg[l],cs[x]=INF;
		return ;
	}
	int mid=(l+r)>>1;
	build(lf,l,mid);
	build(rg,mid+1,r);
	merge(x);
}
void Init()
{
//	freopen("permutation.in","r",stdin);
//	freopen("permutation.out","w",stdout);
	read(n); read(k);
	rep(i,1,n) read(a[i]),p[a[i]]=i;
	rep(i,1,n) {
		deg[p[i]]=query(p[i]+k-1)-query(p[i]-k);
		add(p[i]);
	}
	build(1,1,n);
}
void pushdown(int x)
{
	Min[lf]-=dec[x]; dec[lf]+=dec[x];
	Min[rg]-=dec[x]; dec[rg]+=dec[x];
	dec[x]=0;
}
void recalc(int x,int l,int r)
{
	if (l==r)
	{
		if (Min[x]<1) {
			Min[x]=INF; cs[x]=l;
		}
		return;
	}
	int mid=(l+r)>>1;
	pushdown(x);
	if (Min[lf]<1) recalc(lf,l,mid);
	if (Min[rg]<1) recalc(rg,mid+1,r);
	merge(x);
}
void modify(int x,int L,int R,int l,int r)
{
	if (l>R || r<L) {
		if (Min[x]<1) recalc(x,l,r);
		return;
	}
	if (L<=l && r<=R)
	{
		if (mode==1) cs[x]=INF;
		else {
			Min[x]--; dec[x]++;
		}
		if (Min[x]<1) recalc(x,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(x);
	modify(lf,L,R,l,mid);
	modify(rg,L,R,mid+1,r);
	merge(x);
}
void Solve()
{
	int L,R;
	rep(i,1,n)
	{
		wh=cs[1];
		out[wh]=i;
		mode=1;
		modify(1,wh,wh,1,n);
		mode=2;
		L=max(1,wh-k+1); R=min(n,wh+k-1);
		modify(1,L,R,1,n);
	}
}
void Outit()
{
	rep(i,1,n) printf("%d\n",out[i]);	
}
int main()
{
	Init();
	Solve();
	Outit();
	return 0;
}

Submission Info

Judge Result