Submission #874199

#	Time	Username	Problem	Language	Result	Execution time	Memory
874199		tvladm2009	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	288 ms	29692 KiB

long_mansion

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::vector<std::vector<int>> keys(n + 1), inds(n + 1);
    for (int i = 1; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        int m;
        std::cin >> m;
        keys[i].resize(m);
        for (int j = 0; j < m; j++) {
            std::cin >> keys[i][j];
            inds[keys[i][j]].push_back(i);
        }
    }

    auto check = [&](int l, int r, int x) {
        auto it = lower_bound(inds[x].begin(), inds[x].end(), l);
        return it != inds[x].end() && *it <= r;
    };

    std::vector<int> L(n + 1), R(n + 1), cnt(n + 1, 0);
    auto solve = [&](auto self, int l, int r) -> void {
        if (l > r) {
            return;
        }

        int m = (l + r) / 2;
        self(self, l, m - 1);
        self(self, m + 1, r);

        std::vector<int> left;
        for (int i = m - 1; i >= l; i--) {
            if (R[i] == m - 1 && check(L[i], R[i], a[m - 1])) {
                left.push_back(i);
            }
        }

        std::vector<int> right;
        for (int i = m + 1; i <= r; i++) {
            if (L[i] == m + 1 && check(L[i], R[i], a[m])) {
                right.push_back(i);
            }
        }
        std::vector<int> clr;
        auto add = [&](int i) {
            for (auto x : keys[i]) {
                cnt[x]++;
                clr.push_back(i);
            }
        };

        auto clear = [&]() {
            for (auto it : clr) {
                cnt[it] = 0;
            }
        };

        int ql = m, qr = m;
        auto advance = [&]() {
            while (true) {
                if (ql > l && cnt[a[ql - 1]] > 0) {
                    ql--;
                    add(ql);
                } else if (qr < r && cnt[a[qr]] > 0) {
                    qr++;
                    add(qr);
                } else {
                    break;
                }
            }
        };
        add(m);
        advance();

        L[m] = ql;
        R[m] = qr;
        int last = m;
        for (auto pos : left) {
            for (int j = last; j >= L[pos]; j--) {
                add(j);
            }
            advance();
            L[pos] = ql;
            R[pos] = qr;
            last = L[pos];
        };
        clear();

        ql = m;
        qr = m;
        add(m);
        advance();

        last = m;
        for (auto pos : right) {
            for (int j = last + 1; j <= R[pos]; j++) {
                add(j);
            }
            advance();
            L[pos] = ql;
            R[pos] = qr;
            last = R[pos];
        }
        clear();
    };
    solve(solve, 1, n);

    int q;
    std::cin >> q;
    while (q--) {
        int x, y;
        std::cin >> x >> y;
        std::cout << (y >= L[x] && y <= R[x] ? "YES" : "NO") << "\n";
    }
    return 0;
}

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