Submission #1726512

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#define mp(x,y) make_pair(x,y)
#define ft first
#define sd second
#define rep(i,l,r) for (int i=l;i<=r;++i)
#define P pair<int ,int >
using namespace std;
const int N =2e5+10;
void read(int &x)
{
	x=0;
	char ch=getchar();int f=1;
	while (ch<'0'||ch>'9') ch=='-'?f=-1:0,ch=getchar();
	while ('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x*=f;
}
int n,bo[N],tot,m,a[N],top,v[233],l[N][20],r[N][20],f[1<<20],g[1<<20],cnt,tmp;
P b[N<<1];
void _mx(int &x,int y)
{
	x=max(x,y);
}

void _mn(int &x,int y)
{
	x=min(x,y);
}

int main()
{
	read(n);read(m);
	rep(i,1,n) read(a[i]);
	for (;v[top++]=m;m>>=1);
	rep(i,0,top) 
	{
		int lst=1;
		rep(j,2,n) if (a[j]-a[j-1]>v[i]) 
		{
			rep(k,lst,j-1) l[k][i]=lst,r[k][i]=j-1;
			lst=j;
		}
		rep(k,lst,n) l[k][i]=lst,r[k][i]=n;
	}
	tot=1<<top;--tot;rep(i,0,tot) g[i]=n+1;
	rep(i,0,tot) rep(j,0,top) 
	if (!(i&1<<j)) _mx(f[i|1<<j] ,r[f[i]+1][j]),_mn(g[i|1<<j] ,l[g[i]-1][j]);
	rep(i,0,tot) if (!(i&1)) b[++cnt]=mp(g[i],i);
	rep(i,1,n) b[++cnt]=mp(r[i][0]+1,(1<<top)+i);
	sort(b+1,b+1+cnt);tmp=-1;
	rep(i,1,cnt) if (b[i].sd>(1<<top))
	{
		b[i].sd-=(1<<top);
		if (tmp>=l[b[i].sd][0]-1) bo[b[i].sd]=1;
	}else _mx(tmp,f[((1<<top)-2)^b[i].sd]);
	rep(i,1,n) printf("%s\n",bo[i]?"Possible":"Impossible");
	return 0;
}

Submission Info

Judge Result