Submission #1755814

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

int a[211111];
vector<ii> interval[19];
int pre[(1<<19)+11];
int suf[(1<<19)+11];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,v; cin>>n>>v;
	for(int i=0;i<n;i++) cin>>a[i];
	int cur=v;
	int id=0;
	while(cur)
	{
		int curl=0;
		for(int i=1;i<n;i++)
		{
			if(a[i]-a[i-1]>cur)
			{
				interval[id].pb(mp(curl,i-1));
				curl=i;
			}
		}
		interval[id].pb(mp(curl,n-1));
		cur>>=1; id++;
	}
	for(int i=0;i<n;i++) interval[id].pb(mp(i,i));
	id++;
	pre[0] = -1; suf[0]=n;
	for(int i=1;i<(1<<id);i++)
	{
		pre[i]=-1; suf[i]=n;
		for(int j=0;j<id;j++)
		{
			if(i&(1<<j))
			{
				int mx = pre[i^(1<<j)];
				int tmp=upper_bound(interval[j].begin(),interval[j].end(),mp(mx+2,-1))-interval[j].begin();
				tmp--;
				if(tmp>=0&&tmp<interval[j].size())
				{
					int r=interval[j][tmp].se;
					pre[i]=max(pre[i],r);
				}
				int mn = suf[i^(1<<j)];
				tmp=lower_bound(interval[j].begin(),interval[j].end(),mp(mn,-1))-interval[j].begin();
				tmp--;
				if(tmp>=0&&tmp<interval[j].size())
				{
					int l=interval[j][tmp].fi; 
					suf[i]=min(suf[i],l);
				}
			}
		}
	}
	if(interval[0].size()>20)
	{
		for(int i=0;i<n;i++)
		{
			cout<<"Impossible\n";
		}
		return 0;
	}
	for(int i=0;i<interval[0].size();i++)
	{
		int l=interval[0][i].fi; int r=interval[0][i].se;
		bool pos=0;
		for(int j=0;j<(1<<id);j+=2)
		{
			int tot=(1<<id)-1; tot^=1;
			if(pre[j]>=l-1&&suf[tot^j]<=r+1)
			{
				for(int k=l;k<=r;k++) cout<<"Possible\n";
				pos=1; break;
			}
		}
		if(!pos)
		{
			for(int k=l;k<=r;k++) cout<<"Impossible\n";
		}
	}
}

Submission Info

Judge Result