Submission #1847601

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define x first
#define y second

template<typename T>inline void check_min(T a,T &b){if(a<b)b=a;}
template<typename T>inline void check_max(T a,T &b){if(a>b)b=a;}

namespace yy
{
	const int N=201000,M=N*20;

	struct bit
	{
		bool s[N];
		inline int lowbit(int x){return x&(-x);}
		void init(){memset(s,0,sizeof(s));}
		void inc(int p){p++;for(;p<N;p+=lowbit(p))s[p]=1;}
		bool query(int p){p++;bool ret=0;for(;p;p-=lowbit(p))ret|=s[p];return ret;}
	}T;

	struct node
	{
		int L,R,ty;
		node(int a=0,int b=0,int c=0):L(a),R(b),ty(c){}
		bool operator < (const node &h) const {return L==h.L?R==h.R?ty>h.ty:R<h.R:L>h.L;}
	};

	node s[M];

	int begin[N],next[M*2],to[M*2],w[M*2];
	int pos[N];
	int n,m,e,tot,cnt,S;

	void add(int x,int y,int z,bool k=1)
	{
		to[++e]=y;
		next[e]=begin[x];
		begin[x]=e;
		w[e]=z;
		if(k)add(y,x,z,0);
	}

	void work(int dis,int dep)
	{
//		printf("dep %d : ",dep);
		for(int L=1,R;L<=n;L=R+1)
		{
			for(R=L;R<n && pos[R+1]-pos[R]<=dis;R++);
//			printf("%2d--%2d ",L,R);
			if(dep>1)add(L,R,dep-1);
			else s[++tot]=node(L,R,1);
		}
//		printf("\n");
	}
	void initialize()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",pos+i);
		tot=0,cnt=1;
		for(int tmp=m;;tmp/=2,cnt++)
		{
			work(tmp,cnt);
			if(!tmp)break;
//			printf("e = %d\n",e);
		}
//		printf("cnt = %d\n",cnt);
		S=1<<(cnt-1);
//		printf("S = %d\n",S);
	}

	inline int ins(int k,int i){return k|(1<<(i-1));}
	int f[N*4],g[N*4];

	void dp()
	{
		for(int i=0;i<S;i++)
			f[i]=0,g[i]=n+1;
		for(int k=0;k<S;k++)
		{
			int p=f[k]+1;
			for(int i=begin[p];i;i=next[i])
				if(!(k&(1<<(w[i]-1))))
					check_max(to[i],f[ins(k,w[i])]);
			p=g[k]-1;
			for(int i=begin[p];i;i=next[i])
				if(!(k&(1<<(w[i]-1))))
					check_min(to[i],g[ins(k,w[i])]);
		}
	}

	bool ans[N];

	void solve()
	{
		initialize();
		dp();
		
		for(int k=0;k<S;k++)
			s[++tot]=node(f[k]+1,g[S-k-1]-1,0);
		std::sort(s+1,s+tot+1);
		T.init();

		for(int i=1;i<=tot;i++)
		{
			if(!s[i].ty)T.inc(s[i].R);
			else if(T.query(s[i].R))
			{
				for(int j=s[i].L;j<=s[i].R;j++)
					ans[j]=1;
			}
		}
		for(int i=1;i<=n;i++)
			printf("%s\n",ans[i]?"Possible":"Impossible");
	}
}

int main()
{
	yy::solve();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void yy::initialize()’:
./Main.cpp:61:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&m);
                      ^
./Main.cpp:63:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",pos+i);
                     ^

Judge Result