제출 #1211454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211454		VMaksimoski008	Long Mansion (JOI17_long_mansion)	C++20	20 / 100	695 ms	28528 KiB

long_mansion

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

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

    set<int> pos[n+1];
    for(int i=1; i<=n; i++) {
        int k; cin >> k;
        while(k--) {
            int x; cin >> x;
            pos[x].insert(i);
        }
    }

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

    int mrg = 0;
    vector<int> lp(n+1), rp(n+1);
    for(int i=1; i<=n; i++) {
        lp[i] = rp[i] = i;
        while(true) {
            if(lp[i] > 1 && in(lp[i], rp[i], c[lp[i] - 1])) {
                rp[i] = max(rp[i], rp[lp[i] - 1]);
                lp[i] = lp[lp[i] - 1];
                mrg++;
            } else if(rp[i] < n && in(lp[i], rp[i], c[rp[i]])) {
                rp[i]++;
                mrg++;
            } else break;
        }
    }

    int q; cin >> q;
    while(q--) {
        int x, y; cin >> x >> y;
        cout << (lp[x] <= y && y <= rp[x] ? "YES" : "NO") << '\n';
    }
    assert(mrg <= 4*n);
}

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