Submission #1182198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182198		skibidisigmabartuss69	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	155 ms	57020 KiB

long_mansion

//fast

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

#define ll int64_t
#define ull unsigned long long
#define vi vector <int>
#define vll vector <int64_t>
#define vpi vector <pair <int, int>>
#define vpll vector <pair <int64_t, int64_t>>
#define vpil vector <pair <int, int64_t>>
#define vpli vector <pair <int64_t, int>>
#define vvi vector <vector <int>>
#define vvll vector <vector <int64_t>>
#define iter const auto&
#define pi pair <int, int>
#define pll pair <int64_t, int64_t>
#define pil pair <int, int64_t>
#define pli pair <int64_t, int>
#define all(v) (v).begin(), (v).end()
#define int int_fast32_t
#define Graph vector <basic_string <char32_t>>

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("Os")

void Solve() {
  int n; cin >> n;

  vi doors(n - 1);
  for (auto& i : doors) cin >> i;

  vvi keys(n);
  vi count(n);
  for (int i = 0; i < n; i ++) {
    cin >> count[i];
    keys[i].resize(count[i]);

    for (int j = 0; j < count[i]; j ++) cin >> keys[i][j];
  }

  vi last(n + 1, 0), lef(n + 1);
  for (int i = 1; i <= n - 1; i ++) {
    for (iter key : keys[i - 1]) last[key] = i;

    lef[i] = last[doors[i - 1]];
  }

  fill(all(last), n + 1);
  vi rig(n + 1);

  for (int i = n; i >= 2; i --) {
    for (iter key : keys[i - 1]) last[key] = i;

    rig[i - 1] = last[doors[i - 2]];
  }

  vi left(n + 1), right(n + 1);
  for (int i = 1; i <= n; i ++) {
    left[i] = right[i] = i;

    while (true) {
      bool flag = false;

      if (left[i] > 1 and rig[left[i] - 1] <= right[i]) {
        right[i] = max(right[i], right[left[i] - 1]);
        left[i] = min(left[i], left[left[i] - 1]);
        flag = true;
      }

      if (right[i] < n and left[i] <= lef[right[i]]) {
        right[i] ++;
        flag = true;
      }

      if (!flag) break;
    }
  }

  int q; cin >> q;
  while (q --) {
    int s, t; cin >> s >> t;

    cout << (left[s] <= t and t <= right[s] ? "YES" : "NO") << '\n';
  }
}

int32_t main() {
	cin.tie(0) -> ios_base::sync_with_stdio(0);
	Solve();
}

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