Submission #3053381

---

Source Code Expand

#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

#define fi first
#define se second

namespace io
{
	const int maxb = 1 << 15;
	char b[maxb], *s = b, *t = b;
	bool getchar(char &ch)
	{
		return ch = s == t && (t = (s = b) + fread(b, 1, maxb, stdin)) == b ? 0 : *s ++;
	}
	int getint()
	{
		char ch;
		while (getchar(ch) && (ch < '0' || ch > '9'));
		int s = ch - '0';
		while (getchar(ch) && ch >= '0' && ch <= '9')
			s = s * 10 + ch - '0';
		return s;
	}
}

using io::getint;

template<typename ty> bool Chkmax(ty &x, const ty &y) { return x < y ? x = y, 1 : 0; }
template<typename ty> bool Chkmin(ty &x, const ty &y) { return x > y ? x = y, 1 : 0; }

const int maxn = 5e5 + 10;

int n, k, a[maxn];

struct segment_tree
{
	int M;
	pii T[maxn * 4];
	
	void init()
	{
		for (M = 1; M < n + 2; M <<= 1);
		for (int i = 1; i <= n; ++ i)
			T[i + M] = pii(a[i], i);
		for (int i = M - 1; i; -- i)
			T[i] = max(T[i << 1], T[i << 1 | 1]);
	}
	
	void erase(int x)
	{
		for (T[x += M] = pii(0, 0); x > 1; x >>= 1)
			T[x >> 1] = max(T[x], T[x ^ 1]);
	}
	
	pii query(int s, int t)
	{
		pii res(0, 0);
		for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1)
		{
			if (~ s & 1) Chkmax(res, T[s ^ 1]);
			if (  t & 1) Chkmax(res, T[t ^ 1]);
		}
		return res;
	}
	
} T;

priority_queue<int> Q;
bool inq[maxn];

void insert(int id)
{
	if (!id) return;
	int l = (id - 1) * k + 1, r = min(id * k, n);
	if (l > r) return;
	int pos = T.query(l, r).se;
	if (pos && !inq[pos] && T.query(max(1, pos - k + 1), min(n, pos + k - 1)).se == pos)
	{
		Q.push(pos);
		inq[pos] = true;
	}
}

int ans[maxn];

int main()
{
	n = getint(), k = getint();
	for (int i = 1; i <= n; ++ i) a[i] = getint();
	T.init();
	int tot = (n + k - 1) / k;
	for (int i = 1; i <= tot; ++ i) insert(i);
	for (int i = n; i; -- i)
	{
		int cur = Q.top(); Q.pop();
		ans[cur] = i;
		T.erase(cur);
		cur = (cur + k - 1) / k;
		insert(cur - 1);
		insert(cur);
		insert(cur + 1);
	}
	for (int i = 1; i <= n; ++ i) printf("%d\n", ans[i]);
	return 0;
}

Submission Info

Judge Result