Submission #3244721

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int MAX = 200200;
const int MAXK = 20;

int a[MAX];
int l[MAX][MAXK], r[MAX][MAXK];
int fl[1 << MAXK], fr[1 << MAXK];

int main(void) {
  ios_base::sync_with_stdio(false);

  int N, V;
  cin >> N >> V;
  REP(i, N) cin >> a[i];

  int K = 0;
  int v[MAXK];
  while (V > 0) {
    v[K++] = V;
    V /= 2;
  }
  v[K++] = 0;

  REP(i, N) {
    REP(j, K) {
      if (i > 0 && a[i] - a[i - 1] <= v[j]) {
        l[i][j] = l[i - 1][j];
      } else {
        l[i][j] = i;
      }
    }
  }

  for (int i = N - 1; i >= 0; --i) {
    REP(j, K) {
      if (i < N - 1 && a[i + 1] - a[i] <= v[j]) {
        r[i][j] = r[i + 1][j];
      } else {
        r[i][j] = i;
      }
    }
  }

  REP(s, 1 << K) fl[s] = 0, fr[s] = N - 1;
  REP(s, 1 << K) {
    REP(j, K) {
      if (!(s & (1 << j))) {
        int ns = s | (1 << j);
        int nfl = fl[s] == N ? N : r[fl[s]][j] + 1;
        fl[ns] = max(fl[ns], nfl);
        int nfr = fr[s] == -1 ? -1 : l[fr[s]][j] - 1;
        fr[ns] = min(fr[ns], nfr);
      }
    }
  }

  REP(i, N) {
    bool can = false;

    int all = (1 << K) - 1 - 1;
    REP(s, 1 << K) {
      if ((s & all) == s) {
        if (fl[s] >= l[i][0] && fr[all ^ s] <= r[i][0]) {
          can = true;
          break;
        }
      }
    }
    if (can) {
      cout << "Possible\n";
    } else {
      cout << "Impossible\n";
    }
  }
  return 0;
}

Submission Info

Judge Result