Submission #256810

#	Time	Username	Problem	Language	Result	Execution time	Memory
256810		fedoseevtimofey	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	3061 ms	52996 KiB

long_mansion

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  vector <int> c(n - 1);
  for (int i = 0; i < n - 1; ++i) {
    cin >> c[i];
    --c[i];
  }
  vector <set <int>> who(n);
  vector <set <int>> where(n);
  for (int i = 0; i < n; ++i) {
    int k;
    cin >> k;
    for (int j = 0; j < k; ++j) {
      int x;
      cin >> x;
      --x;
      who[i].insert(x);
      where[x].insert(i);
    }
  }
  vector <int> goR(n, -1);
  goR[n - 1] = n - 1;
  for (int i = n - 2; i >= 0; --i) {
    if (who[i].count(c[i])) goR[i] = goR[i + 1];
    else goR[i] = i;
  }
  auto have = [&] (int l, int r, int x) {
    auto it = where[x].lower_bound(l);
    return (it != where[x].end() && (*it) <= r);
  };
  auto adjust = [&] (int l, int r) {
    while (true) {
      if (l > 0 && have(l, r, c[l - 1])) {
        --l;
      } else if (r + 1 < n && have(l, r, c[r])) {
        ++r;
      } else {
        break;
      }
    }
    return make_pair(l, r);
  };
  vector <pair <int, int>> go(n);
  /*go[0] = {0, goR[0]};
  for (int i = 1; i < n; ++i) {
    int j = goR[i];
    int need = c[i - 1];
    if (have(i, j, need)) {
      go[i] = go[i - 1];
      go[i].second = max(go[i].second, goR[i]);
    } else {
      go[i] = {i, goR[i]};
    }
    go[i] = adjust(go[i].first, go[i].second);
  }*/
  for (int i = 0; i < n; ++i) {
    go[i] = adjust(i, i);
  }
  int q;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    if (go[x].first <= y && y <= go[x].second) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }   
}

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