容易发现跳跃次数为 \(O(\log V)\)。考虑对于跳跃 \(k\) 次后的限制 \(\left\lfloor\frac{V}{2^k}\right\rfloor\)，对每个点预处理出不再跳跃能到达的最左和最右的点 \([l_{k, i}, r_{k, i}]\)。
于是问题变成了，从第 \(i\) 个区间集选择一个区间 \([a_i, b_i]\)，若这些区间的并集是 \([1, n]\)，那么这种方案会使得 \([a_0, b_0]\) 能够到达全部点。
\([a_0, b_0]\) 看起来比较烦。先把第 \(0\) 个区间集扔掉。设当前的区间集的集合为 \(U\)，\(f_S\) 为从 \(S\) 中的每个区间集选出一个区间能覆盖的最大前缀右端点，同时设 \(g_S\) 为能覆盖的最大后缀的左端点。\(f_S, g_S\) 可以状压 dp 求出。枚举覆盖了一段前缀的集合 \(S\)，设 \(T = U \setminus S\)，那么 \(T\) 覆盖了一段后缀。
若 \(f_S + 1 \ge g_T\)，那么 \(U\) 满足从每个区间集选出一个区间能覆盖 \([1, n]\)，此时就是全部 Possible；否则 \([f_S + 1, g_T - 1] \subseteq [a_0, b_0] = [l_{0, f_S + 1}, r_{0, f_S + 1}]\)。若 \(r_{0, f_S + 1} + 1 \ge g_T\) 那么 \([l_{0, f_S + 1}, r_{0, f_S + 1}]\) 就能到达全部点。
时间复杂度 \(O((n + V) \log V)\)。
code
// Problem: E - Camel and Oases
// Contest: AtCoder - AtCoder Grand Contest 012
// URL: https://atcoder.jp/contests/agc012/tasks/agc012_e
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, m, a[maxn], K = -1, b[99], d[maxn], f[maxn * 5], g[maxn * 5];
pii c[20][maxn];
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
ll x = m;
while (x) {
b[++K] = x;
x >>= 1;
}
b[++K] = 0;
reverse(b, b + K + 1);
for (int k = 0; k <= K; ++k) {
for (int i = 1, j = 1; i <= n; i = (++j)) {
while (j < n && a[j + 1] - a[j] <= b[k]) {
++j;
}
for (int l = i; l <= j; ++l) {
c[k][l] = mkp(i, j);
}
}
}
for (int S = 0; S < (1 << K); ++S) {
f[S] = 0;
g[S] = n + 1;
}
for (int S = 0; S < (1 << K); ++S) {
for (int i = 0; i < K; ++i) {
if (S & (1 << i)) {
continue;
}
f[S | (1 << i)] = max(f[S | (1 << i)], c[i][f[S] + 1].scd);
g[S | (1 << i)] = min(g[S | (1 << i)], c[i][g[S] - 1].fst);
}
}
for (int S = 0; S < (1 << K); ++S) {
int T = (1 << K) - 1 - S;
if (f[S] + 1 >= g[T]) {
for (int i = 1; i <= n; ++i) {
puts("Possible");
}
return;
}
pii p = c[K][f[S] + 1];
if (p.scd + 1 >= g[T]) {
++d[p.fst];
--d[p.scd + 1];
}
}
for (int i = 1; i <= n; ++i) {
d[i] += d[i - 1];
puts(d[i] ? "Possible" : "Impossible");
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}