Submission #1359104

---

Source Code Expand

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const double PI=acos(-1);
typedef long long ll;
typedef pair<int,int> pi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)
#define Rep(i,a,b) for (int i=(a);i<(b);i++)
#define Per(i,a,b) for (int i=(a);i>(b);i--)
//debug
#define deb printf("begin\n");
#define dee printf("end\n");
#define def printf("find\n");
#define dey printf("Yes\n");
#define den printf("No\n");
#define dew printf("wrong\n");
void read(int&x){
	x=0;int f=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if (ch=='-')f=-1,ch=getchar();
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=f;
}
//--------------------------head--------------------------//

#define logn 19
#define maxn 200005
int n,v,a[maxn];
int bit[logn],cntbit;

int lowbit(int x){return x&(-x);}


int toL[maxn][logn],fL[1<<logn];
void workL(){
	Rep(j,0,cntbit){toL[1][j]=1;rep(i,1+1,n)
		if (a[i]-a[i-1]<=bit[j])toL[i][j]=toL[i-1][j];
		else toL[i][j]=i;
	}
	/*
	Rep(j,0,cntbit){
		rep(i,1,n)printf("%d ",toL[i][j]);printf("\n");
	}*/
	Rep(i,0,1<<cntbit)fL[i]=n+1;
	Rep(i,0,1<<cntbit){
		for (int j=i;j;j-=lowbit(j))
			fL[i]=min(fL[i],toL[fL[i-lowbit(j)]-1][(int)log2(lowbit(j))]);
	}
	// Rep(i,0,1<<cntbit)printf("%d ",fL[i]);printf("\n");
}

int toR[maxn][logn],fR[1<<logn];
void workR(){
	Rep(j,0,cntbit){toR[n][j]=n;per(i,n-1,1)
		if (a[i+1]-a[i]<=bit[j])toR[i][j]=toR[i+1][j];
		else toR[i][j]=i;
	}
	/*
	Rep(j,0,cntbit){
		rep(i,1,n)printf("%d ",toR[i][j]);printf("\n");
	}*/
	Rep(i,0,1<<cntbit)fR[i]=1-1;
	Rep(i,0,1<<cntbit){
		for (int j=i;j;j-=lowbit(j)){
			// printf("%d %d %d\n",i,lowbit(j),(int)log2(lowbit(j)));
			fR[i]=max(fR[i],toR[fR[i-lowbit(j)]+1][(int)log2(lowbit(j))]);
		}
	}
	// Rep(i,0,1<<cntbit)printf("%d ",fR[i]);printf("\n");
}

int f[maxn][logn];
void work(){
	Rep(i,1,n)f[i][0]=a[i+1]-a[i];
	Rep(j,1,logn)Rep(i,1,n-(1<<j)+1)
		f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	/*
	Rep(j,0,logn){
		Rep(i,1,n-(1<<j)+1)
			printf("%d ",f[i][j]);
		printf("\n");
	}*/
}
int getmax(int L,int R){
	int j=(int)log2(R-L+1);
	return max(f[L][j],f[R-(1<<j)+1][j]);
}

int num_possible[maxn];
int main(){
	//freopen("Camel and Oases.in","r",stdin);
	//freopen("Camel and Oases.out","w",stdout);
	read(n);read(v);rep(i,1,n)read(a[i]);
	for (int i=v;i;i>>=1)bit[cntbit++]=i>>1;
	//rep(i,1,n)printf("%d ",a[i]);printf("\n");
	//Rep(i,0,cntbit)printf("%d ",bit[i]);printf("\n");
	workL();workR();work();
	Rep(i,0,1<<cntbit){
		int R=fL[i]-1,L=fR[((1<<cntbit)-1)^i]+1;
		//printf("%d %d %d %d %d\n",i,((1<<cntbit)-1)^i,L,R,getmax(L,R-1));
		if (L>R){rep(i,1,n)printf("Possible\n");return 0;}
		if (L==R||getmax(L,R-1)<=v)num_possible[L]++,num_possible[R+1]--;
	}
	//rep(i,1,n)printf("%d ",num_possible[i]);printf("\n");
	rep(i,1,n)num_possible[i]+=num_possible[i-1];
	rep(i,1,n)if (num_possible[i])printf("Possible\n");else printf("Impossible\n");
	return 0;
}

Submission Info

Judge Result