Submission #1256836

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define x first
#define y second

int n, v;

int x[200010];

int hn;
int h[20];
int gl[20][200010];
int gr[20][200010];

void in(){
	read(n, v);
	for(int i=1; i<=n; ++i) read(x[i]);
}

void build(){
	int V = v;
	for(;;++hn, V/=2){
		h[hn] = V;
		for(int i=1; i<=n;){
			int j;
			for(j=i+1; j<=n && x[j]-x[j-1] <= V; ++j);
 			for(int k=i; k<j; ++k){
				gl[hn][k]=i;
				gr[hn][k]=j-1;
			}
			i=j;
		}
		if(V == 0) break;
	}
}

int dpL[524288];
int dpR[524288];

void do_dp(){
	int M = (1<<hn);
	for(int i=0; i<M; ++i){
		dpL[i] = 0;
		dpR[i] = n+1;
		for(int j=1; j<=hn; ++j){
			int key = (1 << (j-1));
			if(i & key){
				int bl=dpL[i^key], br=dpR[i^key];
				dpL[i] = max(dpL[i], bl == n ? n : gr[j][bl+1]);
				dpR[i] = min(dpR[i], br == 1 ? 1 : gl[j][br-1]);
			}
		}
	}
}

bool all_yes;
bool yes[200010];
void apply_gugan(int a, int b){
	if(a > b){
		all_yes = true;
	} else {
		if(gl[0][a] == gl[0][b]){
			yes[gl[0][a]]=1;
		}
	}
}

void Fill(){
	int M = (1<<hn);
	for(int i=1; i<M; ++i){
		dpL[i] = max(dpL[i], dpL[i&(i-1)]);
		dpR[i] = min(dpR[i], dpR[i&(i-1)]);
	}
	for(int i=0; i<M; ++i){
		int l=dpL[i]+1;
		int r=dpR[(M-1)^i]-1;
		apply_gugan(l, r);
	}
}

int main()
{
	freopen("in", "r", stdin);
	in(); build(); do_dp(); Fill();
	for(int i=1; i<=n; ++i){
		puts(yes[gl[0][i]]?"Possible":"Impossible");
	}
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void read(int&)’:
./Main.cpp:6:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                                  ^
./Main.cpp: In function ‘void read(ll&)’:
./Main.cpp:7:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                                   ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:92:27: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  freopen("in", "r", stdin);
                           ^

Judge Result