Submission #1161092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161092		fryingduc	Long Mansion (JOI17_long_mansion)	C++20	25 / 100	3078 ms	120444 KiB

long_mansion

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e6 + 6;
const int LG = 20;
int n, q;
int l[maxn], r[maxn];
int bl[maxn][LG + 1], br[maxn][LG + 1];
int L[maxn], R[maxn];
int a[maxn];
vector<int> rv[maxn];

int get_max(int l, int r) {
  int p = 31 - __builtin_clz(r - l + 1);
  return max(br[l][p], br[r - (1 << p) + 1][p]);
}

int get_min(int l, int r) {
  int p = 31 - __builtin_clz(r - l + 1);
  return min(bl[l][p], bl[r - (1 << p) + 1][p]);
}

void solve() {
  cin >> n;
  for (int i = 2; i <= n; ++i) { 
    cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    int sz; cin >> sz;
    for (int j = 1; j <= sz; ++j) {
      int v; cin >> v;
      rv[v].push_back(i);
    }
  }
  for (int i = 1; i <= n; ++i) {
    sort(rv[i].begin(), rv[i].end());
  }
  r[0] = n + 1;
  for (int i = 1; i <= n; ++i) {
    r[i] = n + 1;
    if (i > 1) {
      int x = lower_bound(rv[a[i]].begin(), rv[a[i]].end(), i) - rv[a[i]].begin();
      if (x > 0) {
        int u = rv[a[i]][x - 1];
        l[i] = u;
      }
    }
    if (i < n) {
      int x = upper_bound(rv[a[i + 1]].begin(), rv[a[i + 1]].end(), i) - rv[a[i + 1]].begin();
      if (x < (int)rv[a[i + 1]].size()) {
        int u = rv[a[i + 1]][x];
        r[i] = u;
      }
    }
    bl[i][0] = l[i], br[i][0] = r[i];
  }
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i + (1 << j) <= n + 1; ++i) {
      br[i][j] = max(br[i][j - 1], br[i + (1 << (j - 1))][j - 1]);
      bl[i][j] = min(bl[i][j - 1], bl[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    L[i] = R[i] = i;
    while (true) {
      bool has_expand = 0;
      if (R[i] < n) {
        for (int j = LG; j >= 0; --j) {
          if (R[i] + (1 << j) <= n and bl[R[i] + 1][j] >= L[i]) {
            has_expand = 1;
            R[i] += (1 << j);
          }
        }
      }
      if (L[i] > 1) {
        for (int j = LG; j >= 0; --j) {
          if (L[i] - (1 << j) > 0 and br[L[i] - (1 << j)][j] <= R[i]) {
            has_expand = 1;
            L[i] -= (1 << j);
          }
        }
      }
      if (!has_expand) {
        break;
      }
    }
//    debug(i, L[i], R[i]);
  }
  cin >> q;
  while (q--) {
    int u, v; cin >> u >> v;
    cout << (L[u] <= v and v <= R[u] ? "YES\n" : "NO\n");
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 0 / 75