Submission #1315907

---

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) {
        cout<<len[k]<<": ";
        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);
    //F(k,pl) cout<<bitset<3>(k)<<":"<<rLeft[k]<<" \n"[k==pl-1];
    int start = pl/2;
    int cnt[n+1];
    bool all_ok=false;
    F(i,n+1) cnt[i] = 0;
    F(mleft,start) {
        int le = rLeft[mleft], ri = n - rRight[start-1-mleft];
        //D(le), D(ri);
        if (le >= ri) {
            all_ok = true;
            //P("ALL OK");
        }
        else {
            int ll = (le == n ? n : n-pre[l-1][n-1-le]), rr = (ri == 0 ? 0 : nxt[l-1][ri-1]);
            //printf("[%lld,%lld)\n", ll, rr);
            if (nxt[l-1][ll] == rr) {
                //P(ll<<" to "<<rr);
                cnt[ll]++;
                cnt[rr]--;
            }
        }
        //P("");
    }
    //F(i,n) cout<<cnt[i]<<" \n"[i==n-1];
    cur = 0;
    F(i,n) {
        cur += cnt[i];
        P((all_ok || cur > 0 ? "Possible" : "Impossible"));
    }
}

Submission Info

Judge Result