Submission #43025650

---

Source Code Expand

// LUOGU_RID: 113472244
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
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;
}
const int N = 2e5 + 10;
int n, v, a[N], pp[25][N], qq[25][N], f[1 << 18], g[1 << 18], lim[N];
signed main() {
	// freopen("13.txt", "r", stdin);
	// cout << log2(2e5) + 1 << endl;
	read(n), read(v);
	F(i, 1, n) read(a[i]);
	int k = log2(v) + 1;
	// cout << "! " << log2(3) << endl;
	// cout << k << " " << n << endl;
	F(i, 0, k) {
		// cout << "! " << i << endl;
		int pos = 1;
		F(j, 1, n)
			if (j == n || a[j + 1] - a[j] > (v >> i)) {
				F(k, pos, j) pp[i][k] = j;
				pos = j + 1;
			}
		// puts("%");
		pp[0][n + 1] = n;
		pos = n;
		DF(j, n, 1)
			if (j == 1 || a[j] - a[j - 1] > (v >> i)) {
				// if (i == k) cout << j << endl;
				F(k, j, pos) qq[i][k] = j;
				pos = j - 1;
			}
		// puts("$");
		qq[0][0] = 1;
	}
	// puts("OK");
	int full = (1 << k) - 1;
	F(i, 1, full)
		F(j, 1, k)
			if ((i >> (j - 1)) & 1)
				chkmax(f[i], pp[j][f[i ^ (1 << (j - 1))] + 1]);
	// cout << f[full] << endl;
	g[0] = n + 1;
	F(i, 1, full) {
		g[i] = n;
		F(j, 1, k)
			if ((i >> (j - 1)) & 1)
				chkmin(g[i], qq[j][g[i ^ (1 << (j - 1))] - 1]);
		// cout << "! " << i << " " << g[i] << endl;
	}
	F(i, 1, n) lim[i] = n + 1;
	F(i, 0, full) {
		if (f[i] + 1 >= g[full ^ i]) {
			F(j, 1, n) puts("Possible");
			return 0;
		} chkmin(lim[f[i] + 1], g[full ^ i] - 1);
	}
	DF(i, n - 1, 1) chkmin(lim[i], lim[i + 1]);//, cout << lim[i] << endl;
	F(i, 1, n) {
		// cout << qq[0][i] << " " << pp[0][i] << " " << lim[qq[0][i]] << endl;
		puts(lim[qq[0][i]] <= pp[0][i] ? "Possible" : "Impossible");
	}
	return 0;
}

Submission Info

Judge Result