Submission #1315845

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define P(x) cout << x << endl
#define D(x) P(#x << ": " << x)
#define F(i,n) for (int i=0; i<(int)(n); i++)
#define DEC(i,n) for (int i=(int)(n); --i>=0;)
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
void MI(int &a, int v) {a = min(a,v);}
void MA(int &a, int v) {a = max(a,v);}
const int N=2e5, L=18, PL=1<<L;

int l,n,v,pl;
deque<int> len;

void gen(int x[], int nxt[][N], int reach[]) {
    F(k,l) {
        int cur=0;
        F(i,n+1) {
            if (i == n || (i-1 >= 0 && abs(x[i] - x[i-1]) > len[k])) {
                while (cur < i) {
                    nxt[k][cur] = i;
                    cur++;
                }
            }
        }
    }
    F(mask,pl) {
        reach[mask] = 0;
        F(k,l) if (mask & 1<<k)
            MA(reach[mask], nxt[k][reach[mask-(1<<k)]]);
    }
}

void print(int nxt[][N]) {
    F(k,l) F(i,n) cout<<nxt[k][i]<<" \n"[i==n-1];
}

int x[N], rev[N];
int nxt[L][N], pre[L][N], rLeft[PL], rRight[PL];
bool ok[N];

signed main() {
    cin>>n>>v;
    F(i,n) cin>>x[i], rev[n-1-i] = x[i], ok[i] = false;
    len = {v};
    int cur = v;
    while (cur) cur/=2, len.push_front(cur);
    l = len.size();
    pl = 1<<l;
    gen(x, nxt, rLeft);
    gen(rev, pre, rRight);
    //P("nxt:"); print(nxt);
    //P("pre:"); print(pre);
    bool all_ok=false;
    int start = pl/2;
    F(mleft,start) {
        int le = rLeft[mleft], ri = n - rRight[start-1-mleft];
        if (ri <= le) {
            //P(le<<" to "<<ri<<" all ok");
            //P("for masks "<<mleft<<","<<start-1-mleft);
            all_ok=true;
        }
        else if (nxt[l-1][le] >= ri) {
            int ll = n-pre[l-1][n-le-1], rr = nxt[l-1][ri-1];
            if (ok[ll]) continue;
            //P(ll<<" to "<<rr);
            for (int j=ll; j<rr; j++)
                ok[j] = true;
        }
    }
    F(i,n) P((all_ok || ok[i] ? "Possible" : "Impossible"));
}

Submission Info

Judge Result