Submission #1211421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211421		VMaksimoski008	Long Mansion (JOI17_long_mansion)	C++20	10 / 100	3095 ms	8516 KiB

long_mansion

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e5 + 5;

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);
    for(int i=1; i<n; i++) {
        int x; cin >> x;
        R[i] = x;
        L[i+1] = x;
    }

    vector<int> a[n+1];
    for(int i=1; i<=n; i++) {
        int c; cin >> c;
        while(c--) {
            int x; cin >> x;
            a[i].push_back(x);
        }
    }

    vector<int> lp(n+1), rp(n+1);
    for(int i=1; i<=n; i++) {
        lp[i] = rp[i] = i;
        vector<int> cnt(n+1);
        for(int x : a[i]) cnt[x] = 1;
        while(true) {
            int ok = 0;
            if(lp[i] > 1 && cnt[L[lp[i]]]) {
                lp[i]--;
                ok += 1;
                for(int x : a[lp[i]]) cnt[x] = 1;
            }
            if(rp[i] < n && cnt[R[rp[i]]]) {
                rp[i]++;
                ok += 1;
                for(int x : a[rp[i]]) cnt[x] = 1;
            }
            if(!ok) 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: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75