제출 #1037530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037530		juicy	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	208 ms	52308 KiB

long_mansion

#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;
}

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