Submission #2199103

---

Source Code Expand

#include<cstdio>
#include<cstring>

int n,v,a[200001],fa[200001][21],l[200002][21],r[200002][21],V[21],cnt,fl[1048576],fr[1048576],k,L,R;
bool b[200001];

int ask(int x,int y) {return fa[x][y]==x?x:fa[x][y]=ask(fa[x][y],y);}
int getmin(int a,int b) {return a<b?a:b;}
int getmax(int a,int b) {return a>b?a:b;}

void unite(int x,int y,int z)
{
	int p=ask(x,z),q=ask(y,z);
	if (p==q) return;
	fa[p][z]=q;
	l[q][z]=getmin(l[p][z],l[q][z]);
	r[q][z]=getmax(r[q][z],r[p][z]);
}

int main()
{	
	scanf("%d%d",&n,&v); cnt=-1;
	memset(b,0,sizeof(b));
	for (int i=1; i<=n; i++) scanf("%d",&a[i]);
	while (v) V[++cnt]=v,v>>=1; V[++cnt]=0;
	for (int i=0; i<=cnt; i++)
	{
		for (int j=1; j<=n; j++) fa[j][i]=l[j][i]=r[j][i]=j;
		for (int j=1; j<n; j++) if (a[j+1]-a[j]<=V[i]) unite(j,j+1,i);
	}
	for (int i=0; i<=cnt; i++) r[n+1][i]=n,l[0][i]=1;
	k=(1<<cnt); 
	for (int i=0; i<k; i++) fl[i]=0,fr[i]=n+1;
	for (int i=1; i<k; i++)
		for (int j=0; j<cnt; j++)
			if ((i>>j)&1)
			{
				fl[i]=getmax(fl[i],r[ask(fl[i^(1<<j)]+1,j+1)][j+1]);
				fr[i]=getmin(fr[i],l[ask(fr[i^(1<<j)]-1,j+1)][j+1]);
			}
	for (int i=0; i<k; i++)
	{
		L=fl[i]; R=fr[i^(k-1)];
		if (R<=L+1) 
		{
			for (int j=1; j<=n; j++) printf("Possible\n"); 
			return 0;
		} 
		if (ask(L+1,0)==ask(R-1,0)) b[ask(L+1,0)]=1;
	}
	for (int i=1; i<=n; i++) if (b[ask(i,0)]) printf("Possible\n"); else printf("Impossible\n");
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:22:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&v); cnt=-1;
                     ^
./Main.cpp:24:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=n; i++) scanf("%d",&a[i]);
                                            ^

Judge Result