Submission #1037530

#TimeUsernameProblemLanguageResultExecution timeMemory
1037530juicyLong Mansion (JOI17_long_mansion)C++17
100 / 100
208 ms52308 KiB
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e5 + 5;

int n, q;
int c[N], lt[N], rt[N], lst[N], mi[N], ma[N];
vector<int> key[N];

void dc(int l, int r) {
  if (l == r) {
    mi[l] = ma[l] = l;
    return;
  }
  int md = (l + r) / 2;
  dc(l, md), dc(md + 1, r);
  auto expand = [&](int &L, int &R) {
    bool chg = 1;
    while (chg) {
      chg = 0;
      if (L - 1 >= l && rt[L - 1] <= R) {
        --L;
        chg = 1;
      } 
      if (R < r && lt[R] >= L) {
        ++R;
        chg = 1;
      }
    }
  };
  int L = md + 1, R = md + 1;
  for (int i = md + 1; i <= r; ++i) {
    if (mi[i] == md + 1) {
      R = max(R, ma[i]);
      expand(L, R);
      mi[i] = L, ma[i] = R;
    }
  }
  L = md, R = md;
  for (int i = md; i >= l; --i) {
    if (ma[i] == md) {
      L = min(L, mi[i]);
      expand(L, R);
      mi[i] = L, ma[i] = R;
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 1; i < n; ++i) {
    cin >> c[i];
  }  
  for (int i = 1; i <= n; ++i) {
    int b; cin >> b;
    key[i].resize(b);
    for (int &x : key[i]) {
      cin >> x;
      lst[x] = i;
    }
    lt[i] = lst[c[i]];
  }
  fill(lst, lst + n + 1, n + 1);
  for (int i = n; i > 0; --i) {
    rt[i] = lst[c[i]];
    for (int x : key[i]) {
      lst[x] = i;
    }
  }
  dc(1, n);
  cin >> q;
  while (q--) {
    int x, y; cin >> x >> y;
    cout << (mi[x] <= y && y <= ma[x] ? "YES" : "NO") << "\n";
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...