Submission #2196850

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define per(i,x,y) for (int i=(x); i>=(y); i--)
#define N 131072
#define ll long long
using namespace std;
int n,m,cnt,a[N],b[20],l[20][N],r[20][N],f[N],g[N];
struct node{ int x,y; node(){} node(int a,int b){ x=a,y=b; } }c[N];
const bool cmp(const node &x,const node &y){ return x.y<y.y; }
int main(){
	scanf("%d%d",&n,&m);
	for (; m; m>>=1) b[++cnt]=m; b[++cnt]=0;
	rep (i,1,cnt>>1) swap(b[i],b[cnt-i+1]);
	m=1<<cnt-1;
	rep (i,1,n) scanf("%d",&a[i]);
	rep (i,1,cnt){//预处理l[i][j]和r[i][j]表示第i层第j个点所在线段的左右端点
		l[i][1]=1; r[i][n]=n;
		rep (j,2,n) l[i][j]=a[j]-a[j-1]<=b[i]?l[i][j-1]:j;
		per (j,n-1,1) r[i][j]=a[j+1]-a[j]<=b[i]?r[i][j+1]:j;
	}
	rep (i,0,m-1) g[i]=n+1,f[i]=0;//f[i]表示状态为i，从1开始延伸出去的最远长度；g[i]表示从n开始延伸的最远长度
	//状态s的意思是，如果某位为1则表示当前层选了线段
	rep (i,1,m-1) rep (j,1,cnt-1) if ((i>>j-1)&1){
		int k=i^1<<j-1;//f[k]->f[i]
		f[i]=max(f[i],f[k]<n?r[j][f[k]+1]:n);
		g[i]=min(g[i],g[k]>1?l[j][g[k]-1]:1);
	}
	rep (i,0,m-1)
		if (f[i]+1<g[m-1^i]) c[i+1]=node(f[i]+1,g[m-1^i]-1);
		else{
			rep(j,1,n) puts("Possible"); return 0;
		}
	sort(c+1,c+1+m,cmp);
	for (int i=1,j=1,k=0; i<=n; i++){
		while (j<=m && c[j].y<=r[cnt][i]){
			j++; k=max(k,c[j].x);
		}
		if (k>=l[cnt][i]) puts("Possible"); else puts("Impossible");
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:11:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
./Main.cpp:15:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep (i,1,n) scanf("%d",&a[i]);
                               ^

Judge Result