Submission #1161102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161102		fryingduc	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	540 ms	113072 KiB

long_mansion

#include "bits/stdc++.h"

using namespace std;

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

const int maxn = 5e5 + 5;
const int LG = 19;
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 tree_min[maxn << 2], tree_max[maxn << 2];
void upd(int pos, int ind = 1, int l = 1, int r = n) {
  if (l == r) {
    tree_min[ind] = L[l];
    tree_max[ind] = R[l];
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) upd(pos, ind << 1, l, mid);
  else upd(pos, ind << 1 | 1, mid + 1, r);
  tree_max[ind] = max(tree_max[ind << 1], tree_max[ind << 1 | 1]);
  tree_min[ind] = min(tree_min[ind << 1], tree_min[ind << 1 | 1]);
}

pair<int, int> get(int x, int y, int ind = 1, int l = 1, int r = n) {
  if (l > y || r < x) return make_pair(n + 1, -1);
  if (x <= l and r <= y) {
    return make_pair(tree_min[ind], tree_max[ind]);
  }
  int mid = (l + r) >> 1;
  auto le = get(x, y, ind << 1, l, mid), ri = get(x, y, ind << 1 | 1, mid + 1, r);
  return make_pair(min(le.first, ri.first), max(le.second, ri.second));
}

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;
            auto t = get(L[i] - (1 << j), L[i] - 1);
            L[i] = min(L[i], t.first);
            R[i] = max(R[i], t.second);
          }
        }
      }
      if (!has_expand) {
        break;
      }
    }
    upd(i);
//    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();
  
  cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC << endl;

  return 0;
}

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