Submission #1678896

---

Source Code Expand

// tzl ak IOI! 
 
#include<bits/stdc++.h>
 
#define HEAP priority_queue
#define rep(i, n) for(int i = 0, _end_ = (n); i < _end_; ++i)
#define per(i, n) for(int i = (n) - 1; i >= 0 ; --i)
#define forn(i, l, r) for(int i = (l), _end_ = (r); i <= _end_; ++i)
#define nrof(i, r, l) for(int i = (r), _end_ = (l); i >= _end_; --i)
#define FOR(a, b) for(auto (a): (b))
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define X first
#define Y second
#define eps 1e-6
#define pi 3.1415926535897932384626433832795
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define FILL(a, b) memset((a), (b), sizeof((a)))
#define MCPY(a, b) memcpy((a), (b), sizeof((b)))
 
using namespace std;
 
typedef long long LL;
typedef double flt;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef pair<int,int> pii;
typedef pair<int,LL> pil;
typedef pair<LL,int> pli;
typedef pair<LL,LL> pll;
typedef vector<pil> vil;
typedef vector<pii> vii;
typedef vector<pli> vli;
typedef vector<pll> vll;
 
const int iinf = 1e9 + 7;
const LL linf = 1ll << 60;
const flt dinf = 1e60;
 
template <typename T>
inline void scf(T &x)
{
	bool f = 0; x = 0; char c = getchar();
	while((c < '0' || c > '9') && c != '-') c = getchar();
	if(c == '-') { f = 1; c = getchar(); }
	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
	if(f) x = -x; return;
}
 
template <typename T1, typename T2>
void scf(T1 &x, T2 &y) { scf(x); return scf(y); }
 
template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) { scf(x); scf(y); return scf(z); }
 
template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) { scf(x); scf(y); scf(z); return scf(w); }
 
inline char mygetchar(){ char c = getchar(); while(c == ' ' || c == '\n') c = getchar(); return c; }
 
template <typename T>
void chkmax(T &x, const T &y){ if(y > x) x = y; return; }
 
template <typename T>
void chkmin(T &x, const T &y){ if(y < x) x = y; return; }
 
#ifdef ONLINE_JUDGE
#define debug(x,c) ;
#else
#define DEBUG
#define debug(x,c) cerr<<#x<<"="<<x<<c;
#endif
 
void TZL();
 
void RANK1();
 
#define tzl int
#define ak main
#define IOI ()
tzl ak IOI
{
#undef tzl
#undef ak
#undef IOI
 
	TZL();
	RANK1();
 
#define tzl return
#define caisi 0
#define myy ;
	tzl caisi myy
#undef tzl
#undef caisi
#undef myy
}
 
//---------------------------head----------------------------
 
const int N = 2e5 + 100;
const int lgN = 20;
 
int n, V, m;
int x[N];
int lb[lgN][N], rb[lgN][N];
vii seg[lgN];
int dpl[1048576], dpr[1048576];
 
void get_seg()
{
	for(int i = 1, j; i <= n; i = j)
	{
		j = i + 1;
		while(j <= n && x[j] - x[j - 1] <= V) ++j;
		seg[m].pb({i, j - 1});
	}
	for(auto x: seg[m])
	{
		int l = x.X, r = x.Y;
		forn(i, l, r) lb[m][i] = l, rb[m][i] = r;
	}
	++m;
	return;
}
 
void TZL()
{
	scf(n, V);
	forn(i, 1, n) scf(x[i]);
	while(V)
	{
		get_seg();
		V >>= 1;
	}
	forn(i, 1, n) lb[m][i] = i, rb[m][i] = i;
	++m;
	return;
}
 
void DPL()
{
	forn(msk, 1, (1 << m) - 1)
	{
		rep(i, m) if((msk >> i) & 1)
		{
			chkmax(dpl[msk], dpl[msk ^ (1 << i)]);
			chkmax(dpl[msk], rb[i][dpl[msk ^ (1 << i)] + 1]);
		}
	}
	return;
}
 
void DPR()
{
	dpr[0] = n + 1;
	forn(msk, 1, (1 << m) - 1)
	{
		dpr[msk] = n + 1;
		rep(i, m) if((msk >> i) & 1)
		{
			chkmin(dpr[msk], dpr[msk ^ (1 << i)]);
			chkmin(dpr[msk], lb[i][dpr[msk ^ (1 << i)] - 1]);
		}
	}
	return;
}
 
vii all;
bool ans[N];
int TOT;
 
void check(int l, int r)
{
	for(int msk = 0; msk < (1 << m); msk += 2)
	{
		int lb = dpl[msk], rb = dpr[TOT ^ msk];
		if(l <= lb + 1 && r >= rb - 1)
		{
			forn(i, l, r) ans[i] = 1;
			return;
		}
	}
	return;
}
 
void RANK1()
{
	if(SZ(seg[0]) <= m)
	{
		DPL(); DPR();
		TOT = (1 << m) - 2;
		for(auto x: seg[0]) check(x.X, x.Y);
	}
	forn(i, 1, n) puts(ans[i] ? "Possible" : "Impossible");
	return;
}

Submission Info

Judge Result