Submission #1285473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285473		lmquan	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	571 ms	29584 KiB

long_mansion

#define taskname ""
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> c(n);
  for (int i = 1; i < n; i++) {
    cin >> c[i];
  }
  vector<vector<int>> b(n + 1);
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    for (int j = 1; j <= x; j++) {
      int a;
      cin >> a;
      b[a].push_back(i);
    }
  }

  auto f = [&](int k, int l, int r) -> bool {
    auto it = upper_bound(b[k].begin(), b[k].end(), r);
    if (it == b[k].begin() || *(--it) < l) {
      return false;
    }
    return true;
  };

  vector<pair<int, int>> d(n + 1, {n + 1, -1});
  vector<int> p(n);
  iota(p.begin(), p.end(), 1);
  shuffle(p.begin(), p.end(), rng);

  for (int i : p) {
    int l = i, r = i;
    while (true) {
      if (l > 1 && f(c[l - 1], l, r)) {
        int t = l - 1;
        l = min(l - 1, d[t].first);
        r = max(r, d[t].second);
      } else if (r < n && f(c[r], l, r)) {
        int t = r + 1;
        r = max(r + 1, d[t].second);
        l = min(l, d[t].first);
      } else {
        break;
      }
    }
    d[i] = {l, r};
  }

  int q;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    cout << (d[x].first <= y && y <= d[x].second ? "YES" : "NO") << '\n';
  }

  return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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