Submission #1237242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237242		duckindog	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	154 ms	41280 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

const int N = 500'000 + 10;
int n, q;
int c[N];
vector<int> a[N];

int last[N], pre[N], nxt[N];
int st[N], ed[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);


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

    { // cal pre & nxt
        for (int i = 1; i < n; ++i) { 
            for (const auto& x : a[i]) last[x] = i;
            pre[i + 1] = last[c[i]];
        }
        fill(last + 1, last + n + 1, n + 1);
        for (int i = n; i > 1; --i) { 
            for (const auto& x : a[i]) last[x] = i;
            nxt[i - 1] = last[c[i - 1]];
        }
    }
    
    for (int i = 1; i <= n; ++i) { 
        st[i] = ed[i] = i;
        while ((1 < st[i] && nxt[st[i] - 1] <= ed[i]) || (ed[i] < n && pre[ed[i] + 1] >= st[i])) { 
            if (1 < st[i] && nxt[st[i] - 1] <= ed[i]) {
                tie(st[i], ed[i]) = make_pair(min(st[i], st[st[i] - 1]), max(ed[i], ed[st[i] - 1]));
            }
            if (ed[i] < n && pre[ed[i] + 1] >= st[i]) ed[i] += 1;
        }
    }

    cin >> q;
    while (q--) { 
        int x, y; cin >> x >> y;
        cout << (st[x] <= y && y <= ed[x] ? "YES" : "NO") << "\n";
    }
}

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