Submission #2215803

---

Source Code Expand

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 220000
inline char gc(){
	static char now[1<<16],*S,*T;
	if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
	return *S++;
}
#define S 1<<19
inline int read(){
	int x=0,f=1;char ch=gc();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
	while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}
	return x*f;
}
int f1[S],f2[S],n,num,bin[20],st[N],a[N],right[N][20],left[N][20],v;
int main(){
//	freopen("agc.in","r",stdin);
	n=read();v=read();int Log=0;
	for (int i=1;i<=n;++i) a[i]=read();
	while ((1<<Log)<=v) Log++;Log++;
	for (int i=0;i<=Log+1;++i) bin[i]=1<<i;
	num=1;for (int i=2;i<=n;++i) if (a[i]-a[i-1]>v) num++;
	for (int j=0;j<Log;++j){
		left[1][j]=1;right[n][j]=n;
		for (int i=2;i<=n;++i) if (a[i]-a[i-1]>(v>>j)) left[i][j]=i;else left[i][j]=left[i-1][j];
		for (int i=n-1;i>=1;--i) if (a[i+1]-a[i]>(v>>j)) right[i][j]=i;else right[i][j]=right[i+1][j];
	}	
	/*for (int j=0;j<Log;++j){
		for (int i=1;i<=n;++i) printf("%d ",right[i][j]);printf("\n");
		for (int i=n;i>=1;--i) printf("%d ",left[i][j]);printf("\n");
	}*/
	if (num>Log){
		for (int i=1;i<=n;++i) printf("Impossible\n");return 0;
	}
	for (int s=0;s<=bin[Log]-1;++s) {f1[s]=0,f2[s]=n+1;}
	for (int s=0;s<=bin[Log]-1;++s){
		for (int i=0;i<Log;++i){
			if (s&bin[i])continue;
			if (f1[s]==n) f1[s|bin[i]]=n;else f1[s|bin[i]]=max(f1[s|bin[i]],right[f1[s]+1][Log-i-1]);
			if (f2[s]==1) f2[s|bin[i]]=1;else f2[s|bin[i]]=min(f2[s|bin[i]],left[f2[s]-1][Log-i-1]);
		}
	}for (int i=0;i<=n;++i) st[i]=n+2;
	for (int s=0;s<=bin[Log-1]-1;++s){
		int s1=(bin[Log-1]-1)^s;
		st[f1[s]]=min(st[f1[s]],f2[s1]);
	} for (int i=n-1;i>=0;--i) st[i]=min(st[i],st[i+1]);
	//for (int i=0;i<=n;++i) printf("%d ",st[i]);printf("\n");
	for (int i=1;i<=n;++i){
		int l=left[i][0],r=right[i][0];
		if (st[l-1]<=r+1) printf("Possible\n");else printf("Impossible\n");
	}
	return 0;
}

Submission Info

Judge Result