Submission #2215432

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int L[20][222222],R[20][222222];

int N,V;
int X[222222];


int dp1[1<<18];
int dp2[1<<18];


int acc[222222];

signed main(){
    cin>>N>>V;
    rep(i,N)cin>>X[i];
    rep(k,20){
        rep(i,N){
            L[k][i]=i;
            if(i&&X[i]-X[i-1]<=(V>>k))L[k][i]=L[k][i-1];
        }
        for(int i=N-1;i>=0;i--){
            R[k][i]=i;
            if(i+1!=N&&X[i+1]-X[i]<=(V>>k))R[k][i]=R[k][i+1];
        }
    }

    rep(i,1<<18){
        rep(j,18){
            if(i>>j&1)continue;
            if((V>>j)==0)chmax(dp1[i|(1<<j)],dp1[i]);
            else if(dp1[i]==N)dp1[i|(1<<j)]=N;
            else chmax(dp1[i|(1<<j)],R[j+1][dp1[i]]+1);
        }
    }

    rep(i,1<<18)dp2[i]=N-1;
    rep(i,1<<18){
        rep(j,18){
            if(i>>j&1)continue;
            if((V>>j)==0)chmin(dp2[i|(1<<j)],dp2[i]);
            else if(dp2[i]==-1)dp2[i|(1<<j)]=-1;
            else chmin(dp2[i|(1<<j)],L[j+1][dp2[i]]-1);
        }
    }

    rep(i,1<<18){
        int j=(1<<18)-1-i;

        if(dp1[i]>dp2[j]){
            acc[0]++;
            continue;
        }


        if(R[0][dp1[i]]>=dp2[j]){
            acc[L[0][dp1[i]]]++;
            acc[R[0][dp1[i]]+1]--;
        }
    }

    rep(i,N){
        acc[i+1]+=acc[i];
        if(acc[i]){
            puts("Possible");
        }
        else{
            puts("Impossible");
        }
    }
    return 0;
}

Submission Info

Judge Result