Submission #1350837

#TimeUsernameProblemLanguageResultExecution timeMemory
1350837msab3fLong Mansion (JOI17_long_mansion)C++20
100 / 100
206 ms51168 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 500'000 + 10;

int n, c[MAX_N], b[MAX_N], bwd[MAX_N], fwd[MAX_N], q, cnt;
vector<int> a[MAX_N], a_t[MAX_N];
bool tmp[MAX_N];

int get_next(int x, int pos) {
    auto it = lower_bound(a_t[x].begin(), a_t[x].end(), pos);
    if (it == a_t[x].end()) return n + 1;
    return *it;
}

int get_before(int x, int pos) {
    auto it = upper_bound(a_t[x].begin(), a_t[x].end(), pos);
    if (it == a_t[x].begin()) return 0;
    return *(--it);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n - 1; ++i) {
        cin >> c[i];
    }

    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        a[i].resize(b[i]);
        for (int &x : a[i]) {
            cin >> x;
            a_t[x].push_back(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        bwd[i] = fwd[i] = i;
    }

    for (int i = 1; i <= n; ++i) {
        auto check_fwd = [&] () {
            return fwd[i] < n && get_before(c[fwd[i]], fwd[i]) >= bwd[i];
        };
        auto check_bwd = [&] () {
            return bwd[i] > 1 && get_next(c[bwd[i] - 1], bwd[i]) <= fwd[i];
        };
        while (check_fwd() || check_bwd()) {
            ++cnt;
            if (check_bwd()) {
                fwd[i] = max(fwd[i], fwd[bwd[i] - 1]);
                bwd[i] = bwd[bwd[i] - 1];
            } else {
                bwd[i] = min(bwd[i], bwd[fwd[i] + 1]);
                fwd[i] = fwd[fwd[i] + 1];
            }
        }
    }

    cin >> q;

    while (q--) {
        int x, y;
        cin >> x >> y;
        if (bwd[x] <= y && y <= fwd[x]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...