Submission #1843431

---

Source Code Expand

#include <cstdio>
#include <iostream>
inline int Get() {
	char ch;
	int Num, Sign = 0;
	while ((ch = getchar()) < '0' || ch > '9')
		if (ch == '-') Sign ^= 1;
	Num = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9')
		Num = (Num << 3) + (Num << 1) + ch - '0';
	return Sign ? -Num : Num;
}
const int N = 2e5 + 5;
int n, m, pos[N], a[20], len, toL[20][N], toR[20][N];
int all, preL[1 << 20], preR[1 << 20], flag[N];
inline int queryL(int x) {
	int l = 1, r = n, res = 1;
	while (l <= r) {
		int mid = l + r >> 1;
		if (toL[len][mid] <= x) res = mid, l = mid + 1;
		else r = mid - 1;
	}
	return res;
}
inline int queryR(int x) {
	int l = 1, r = n, res = 1;
	while (l <= r) {
		int mid = l + r >> 1;
		if (toR[len][mid] >= x) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	return res;
}
int main() {
	n = Get(), m = Get();
	for (int i = 1; i <= n; ++i) pos[i] = Get();
	
	for (int x = m; x; x >>= 1) a[len++] = x >> 1; a[len] = m;
	
	for (int k = 0; k <= len; ++k) {
		toL[k][1] = 1; 
		for (int i = 2; i <= n; ++i) toL[k][i] = (pos[i] - pos[i - 1] <= a[k]) ? toL[k][i - 1] : i;
		
		toR[k][n] = n; 
		for (int i = n - 1; i; --i) toR[k][i] = (pos[i + 1] - pos[i] <= a[k]) ? toR[k][i + 1] : i;
	}
	
	all = 1 << len;
	for (int opt = 0; opt < all; ++opt) preL[opt] = 0;
	for (int opt = 1; opt < all; ++opt) 
		for (int k = 0; k < len; ++k)
			if (opt & (1 << k)) {
				int nxt = opt ^ (1 << k);
				preL[opt] = std :: max(preL[opt], preL[nxt]);
				if (preL[nxt] < n) preL[opt] = std :: max(preL[opt], toR[k][preL[nxt] + 1]);
			}
			
	for (int opt = 0; opt < all; ++opt) preR[opt] = n + 1;
	for (int opt = 1; opt < all; ++opt) 
		for (int k = 0; k < len; ++k)
			if (opt & (1 << k)) {
				int nxt = opt ^ (1 << k);
				preR[opt] = std :: min(preR[opt], preR[nxt]);
				if (preR[nxt] > 1) preR[opt] = std :: min(preR[opt], toL[k][preR[nxt] - 1]);
			}
	
	for (int opt = 0; opt < all; ++opt) {
		int x = queryR(preR[(all - 1) ^ opt] - 1), y = queryL(preL[opt] + 1);
		if (x <= y) ++flag[x], --flag[y + 1];
	}
	
	for (int i = 1; i <= n; ++i) 
		flag[i] += flag[i - 1], puts(flag[i] ? "Possible" : "Impossible");
}

Submission Info

Judge Result