Submission #1256663

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int n, v, lg, a[200005];

struct oneside {
	int rb[19][200005], dt[1<<19];
	int solve () {
		int cv = v;
		for(int i=0;i<=lg;i++,cv/=2) {
			int un = 1;
			for(int j=1;j<n;j++) {
				if(a[j+1] - a[j] > cv) {
					for(int k=un;k<=j;k++) rb[i][k] = j;
					un = j+1;
				}
			}
			for(int k=un;k<=n;k++) rb[i][k] = n;
		}
		for(int i=0;i<(1<<lg);i++) {
			for(int j=1;j<=lg;j++) {
				int t = (1<<(j-1));
				if(i & t) continue;
				dt[i|t] = max(dt[i|t], rb[j][min(dt[i]+1, n)]);
			}
		}
	}
} ls, rs;

struct segtree {
	int val[888888], lim;
	void init () {
		for(lim = 1; lim <= n; lim <<= 1);
	}
	void update (int S, int E, int X) {
		S += lim; E += lim;
		while(S<=E) {
			if(S%2 == 1) val[S] += X, S++;
			if(E%2 == 0) val[E] += X, E--;
			S>>=1; E>>=1;
		}
	}
	int query (int P) {
		P += lim;
		int ret = 0;
		while(P) {
			ret += val[P];
			P>>=1;
		}
		return ret;
	}
} seg;

int main()
{
	scanf("%d%d",&n,&v);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	for(int i=v;i;i/=2,lg++);
	ls.solve();
	reverse(a+1, a+1+n);
	for(int i=1;i<=n;i++) a[i] *= -1;
	rs.solve();
	seg.init();
	for(int i=0;i<(1<<lg);i++) {
		int t = ((1<<lg)-1)^i;
		if(ls.dt[i] + 1 > n - rs.dt[t]) {
			for(int j=1;j<=n;j++) puts("Possible");
			return 0;
		}
		else {
			int ss = n - rs.rb[0][min(n, rs.dt[t]+1)] + 1, se = ls.rb[0][min(n, ls.dt[i]+1)];
			if(ss <= se) seg.update(ss, se, 1);
		}
	}
	for(int i=1;i<=n;i++) {
		puts(seg.query(i) ? "Possible" : "Impossible");
	}
}

Submission Info

Compile Error

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

Judge Result