Submission #3418124

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const int inf = 0x3f3f3f3f;

int n, k, E;
int p[N], q[N];
int tr[N << 2], ans1[N], ans2[N];
int fir[N], deg[N], nex[N << 1], arr[N << 1];
priority_queue<int, vector<int>, greater<int> > Q;

inline void Add_Edge(int x, int y) {
//	cout << x << ' ' << y << endl;
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y; deg[y]++;
}

void Updata(int x, int l, int r, int pos, int v) {
	if (l == r) return (void) (tr[x] = v);
	int mid = (l + r) >> 1;
	if (mid >= pos)
		Updata(x << 1, l, mid, pos, v);
	if (mid < pos)
		Updata(x << 1 | 1, mid + 1, r, pos, v);
	tr[x] = min(tr[x << 1], tr[x << 1 | 1]);
}

int Query(int x, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return tr[x];
	int mid = (l + r) >> 1, ans = 0x3f3f3f3f;
	if (mid >= ql)
		ans = min(ans, Query(x << 1, l, mid, ql, qr));
	if (mid < qr)
		ans = min(ans, Query(x << 1 | 1, mid + 1, r, ql, qr));
	return ans;
}
	
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &p[i]);
		q[p[i]] = i;
	}
/*	for (int i = 1; i <= n; ++i)
		cout << q[i] << ' ';
		puts("");*/
	memset(tr, 0x3f, sizeof tr);
	for (int i = n; i >= 1; --i) {
		int x = Query(1, 1, n, min(n, q[i] + 1), min(n, q[i] + k - 1));
		int y = Query(1, 1, n, max(1, q[i] - k + 1), max(1, q[i] - 1));
//		cout << i << ' ' << x << ' ' << y << endl;
		if (x != inf) Add_Edge(q[i], q[x]);
		if (y != inf) Add_Edge(q[i], q[y]);
		Updata(1, 1, n, q[i], i);
	}
	for (int i = 1; i <= n; ++i)
		if (!deg[i]) Q.push(i);
	int cnt = 0;
	while (!Q.empty()) {
		int x = Q.top(); Q.pop();
		for (int i = fir[x]; i; i = nex[i]) {
			if (--deg[arr[i]] == 0) Q.push(arr[i]);
		}
		ans1[++cnt] = x;
	}
	for (int i = 1; i <= n; ++i)
		ans2[ans1[i]] = i;
/*	for (int i = 1; i <= n; ++i)
		cout << ans1[i] << ' ';
		puts("");*/
	for (int i = 1; i <= n; ++i)
		printf("%d\n", ans2[i]);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:39:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
./Main.cpp:41:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[i]);
                     ^

Judge Result