Submission #1211444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211444		VMaksimoski008	Long Mansion (JOI17_long_mansion)	C++20	0 / 100	3095 ms	33628 KiB

long_mansion

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

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n; cin >> n;
    vector<int> L(n+1), R(n+1), a[n+1];
    for(int i=1; i<n; i++) {
        int x; cin >> x;
        R[i] = x;
        L[i+1] = x;
    }
    
    set<int> pos[n+1];
    for(int i=1; i<=n; i++) {
        int c; cin >> c;
        while(c--) {
            int x; cin >> x;
            a[i].push_back(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;
    };

    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], L[lp[i]])) {
                lp[i] = lp[lp[i]-1];
                rp[i] = max(rp[i], rp[lp[i]-1]);
            } else if(rp[i] < n && in(lp[i], rp[i], R[rp[i]])) {
                rp[i]++;
            } else break;
        }
    }
    
    int q; cin >> q;
    while(q--) {
        int x, y; cin >> x >> y;
        cout << (lp[x] <= y && y <= rp[x] ? "YES" : "NO") << '\n';
    }
}

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