Submission #1834161

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define ri rd<int>
using namespace std;
const int maxN = 2e5 + 7;
const int maxV = 20;
const int maxS = (1 << maxV);

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

inline void Min(int &x, int y) {if (y < x) x = y;}
inline void Max(int &x, int y) {if (y > x) x = y;}

int n, m, V;
int a[maxN], b[maxN];
int nx[maxV][maxN], pr[maxV][maxN];
int f[maxS], g[maxS];

struct dsu {
	int mn, mx, fa;
}fa[maxN];

inline int find(int x) {return (fa[x].fa != x) ? fa[x].fa = find(fa[x].fa) : x;}

void merge(int x, int y) {
	if (find(x) != find(y)) {
		Min(fa[find(y)].mn, fa[find(x)].mn);
		Max(fa[find(y)].mx, fa[find(x)].mx);
		fa[find(x)].fa = find(y);
	}
}

struct rec {
	int l, r;
	inline bool operator < (const rec &v) const {
		return r < v.r;
	}
}q[maxS]; int tt;

int main() {

	n = ri(), m = ri();
	rep (i, 1, n) a[i] = ri();
	for (int i = m; i > 0; i >>= 1) b[++V] = i; b[++V] = 0;
	reverse(b+1, b+V+1);
	
	rep (i, 1, n) fa[i] = (dsu){i, i, i};

	rep (j, 1, V) {
		rep (i, 2, n) if (a[i] - a[i - 1] <= b[j]) merge(i, i-1);
		rep (i, 1, n) nx[j][i] = fa[find(i)].mx, pr[j][i] = fa[find(i)].mn;
		nx[j][n+1] = n;
		pr[j][0] = 1;
	}

	int mask = (1 << V) - 1;
	f[0] = 0;
	rep (s, 1, mask) {
		f[s] = 0;
		rep (j, 1, V) if (s >> (j-1) & 1)
			Max(f[s], nx[j][f[s ^ (1 << (j-1))] + 1]);
	}
	g[0] = n+1;
	rep (s, 1, mask) {
		g[s] = n+1;
		rep (j, 1, V) if (s >> (j-1) & 1)
			Min(g[s], pr[j][g[s ^ (1 << (j-1))] - 1]);
	}

	rep (s, 0, mask = (1 << (V-1)) - 1)
		q[++tt] = (rec){f[s], g[mask ^ s]};
	sort(q+1, q+tt+1);

	for (int i = 1, j = 1, cl = -1; i <= n; ++ i) {
		int l = fa[find(i)].mn, r = fa[find(i)].mx;
		for (; j <= tt && q[j].r <= r+1; ++ j) cl = max(cl, q[j].l);
		puts(cl >= l - 1 ? "Possible" : "Impossible");
	}

	return 0;
}

Submission Info

Judge Result