Submission #1242771

---

Source Code Expand

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int maxL[20][200005], maxR[20][200005];
int p_L, p_R;
int dpL[(1<<20)], dpR[(1<<20)]; // dpL prefix, dpR suffix
int N, V;
ll x[200005];
int BIT[200005]; // indexes are reversed
int parts[200005];
vector <pii> dp_range;

int calc_dpL(int mask) {
	if (mask == 0) return 0;
	int &ret = dpL[mask];
	int tmp;
	if (ret != -1) return ret;
	ret = 0;
	for (int i=0;i<20;++i) {
		if (mask&(1<<i)) {
			if (calc_dpL(mask - (1<<i)) == N) ret = N;
			else {
				tmp = calc_dpL(mask-(1<<i));
				tmp = maxR[i][tmp] - tmp + 1;
				ret = max(ret,tmp + calc_dpL(mask-(1<<i)));
			}
		}
	}
	return ret;
}

int calc_dpR(int mask) {
	//cout << mask << endl;
	if (mask == 0) return 0;
	int &ret = dpR[mask];
	int tmp;
	if (ret != -1) return ret;
	ret = 0;
	for (int i=0;i<20;++i) {
		if (mask&(1<<i)) {
			if (calc_dpR(mask - (1<<i)) == N) ret = N;
			else {
				tmp = (N-1) - calc_dpR(mask-(1<<i));
				tmp = tmp - maxL[i][tmp] + 1;
				ret = max(ret,tmp + calc_dpR(mask-(1<<i)));
			}
		}
	}
	return ret;
}

bool cmp(pii a, pii b) {
	return a.se < b.se;
}

int BIT_q(int u) {
	++u;
	int ret = -1;
	while (u) {
		ret=max(ret,BIT[u]);
		u-=u&(-u);
	}
	return ret;
}

void BIT_u(int u,int val) {
	++u;
	for (;u<200005;u+=u&(-u)) BIT[u]=max(BIT[u],val);
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	memset(dpL,-1,sizeof(dpL));
	memset(dpR,-1,sizeof(dpR));
	memset(BIT,-1,sizeof(BIT));
	parts[0]=1;
	for (int i=1;i<200005;++i) {
		parts[i] = 1+parts[i>>1];
	}
	cin >> N >> V;
	for (int i=0;i<N;++i)
		cin >> x[i];
	for (int i=0;i<20;++i) {
		for (int j=N;j>=0;--j) {
			maxR[i][j]=j;
			if ( j+1 < N && x[j+1]-x[j] <= (V>>i) ) maxR[i][j] = maxR[i][j+1];
		}
	}
	for (int i=0;i<20;++i) {
		for (int j=0;j<=N;++j) {
			maxL[i][j]=j;
			if ( j-1 >= 0 && x[j]-x[j-1] <= (V>>i) ) maxL[i][j] = maxL[i][j-1];
		}
	}
	int mask_r;
	for (int mask_l=0;mask_l<(1<<parts[V]);mask_l+=2) {
		mask_r = ((1<<parts[V]) - 1) - mask_l - 1;
		dp_range.push_back(make_pair(calc_dpL(mask_l),calc_dpR(mask_r)));
	}
	sort(dp_range.begin(), dp_range.end(), cmp);
	for (int i=0;i<(int)dp_range.size();++i) {
		BIT_u(N - dp_range[i].fi,dp_range[i].se);
	}
	for (int i=0;i<N;++i) {
		p_L = maxL[0][i];
		p_R = maxR[0][i];
		if (BIT_q(N - p_L) >= N-(p_R+1)) cout << "Possible\n";
		else cout << "Impossible\n";
	}
	return 0;
}

Submission Info

Judge Result