Submission #1653881

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define MAXN	400005
#define MAXLOG	20
int n, k, v[MAXLOG], x[MAXN];
int l[MAXLOG][MAXN], r[MAXLOG][MAXN];
int lft[MAXN], rit[MAXN], opt[MAXN];
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int main() {
	read(n), read(v[0]);
	for (int i = 1; i <= n; i++)
		read(x[i]);
	for (k = 1; v[k - 1] != 0; k++)
		v[k] = v[k - 1] / 2;
	k -= 1; int goal = (1 << k) - 1;
	for (int j = 0; j <= k; j++) {
		l[j][1] = 1;
		for (int i = 2; i <= n; i++)
			if (x[i] - x[i - 1] <= v[j]) l[j][i] = l[j][i - 1];
			else l[j][i] = i;
	}
	for (int j = 0; j <= k; j++) {
		r[j][n] = n;
		for (int i = n - 1; i >= 1; i--)
			if (x[i + 1] - x[i] <= v[j]) r[j][i] = r[j][i + 1];
			else r[j][i] = i;
	}
	for (int curr = 0; curr <= goal; curr++) {
		lft[curr] = 0;
		rit[curr] = n + 1;
	}
	for (int curr = 0; curr < goal; curr++)
	for (int i = 1, j = 1; i <= k; i++, j <<= 1) {
		if (curr & j) continue;
		int dest = curr | j;
		lft[dest] = max(lft[dest], min(r[i][lft[curr] + 1], n));
		rit[dest] = min(rit[dest], max(l[i][rit[curr] - 1], 1));
	}
	for (int i = 0; i <= n; i++)
		opt[i] = n + 2;
	for (int curr = 0; curr <= goal; curr++)
		opt[lft[curr]] = min(rit[goal ^ curr], opt[lft[curr]]);
	for (int i = n - 1; i >= 0; i--)
		opt[i] = min(opt[i], opt[i + 1]);
	for (int i = 1; i <= n; i++) {
		int lft = l[0][i];
		int rit = r[0][i];
		if (opt[lft - 1] <= rit + 1) printf("Possible\n");
		else printf("Impossible\n");
	}
	return 0;
}

Submission Info

Judge Result