Submission #334362

#	Time	Username	Problem	Language	Result	Execution time	Memory
334362		12tqian	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	3079 ms	14572 KiB

long_mansion

#include <bits/stdc++.h>

int main() {
    using namespace std;
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    vector<int> c(n);
    c.back() = -1;
    for (int i = 0; i < n - 1; i++)
        cin >> c[i], c[i]--;
    vector<vector<int>> a(n);
    vector<int> b(n);
    for (int i = 0; i < n; i++ ) {
        cin >> b[i];
        a[i].resize(b[i]);
        for (int j = 0; j < b[i]; j++)
            cin >> a[i][j], a[i][j]--;
        sort(a[i].begin(), a[i].end());
    }
    vector<int> L(n), R(n); // how far you can go left and right with going both left and right
    // first compute how far you can go right only going right
    vector<vector<int>> loc(n);
    for (int i = 0; i < n; i++) 
        for (int key : a[i]) 
            loc[key].push_back(i);
    auto get = [&](int t, int l, int r) -> int {
        // gets the number of keys in the range [l, r]
        // of type t
        auto it2 = upper_bound(loc[t].begin(), loc[t].end(), r);
        if (it2 == loc[t].begin()) 
            return 0;
        it2 = prev(it2);
        auto it1 = lower_bound(loc[t].begin(), loc[t].end(), l);
        return it2 - it1 + 1;
    };
    vector<int> go(n); // how far can you go purely to the right
    for (int i = n - 1; i >= 0; i--) {
        go[i] = i;
        while (binary_search(a[i].begin(), a[i].end(), c[go[i]]))
            go[i] = go[go[i] + 1];
    }
    for (int i = 0; i < n; i++) {
        // first check if you can go left
        if (i) {
            R[i] = go[i];
            L[i] = i;
            if (get(c[i - 1], i, R[i])) {
                L[i] = L[i - 1];
                while (true) {
                    bool ok = false;
                    if (L[i] && get(c[L[i] - 1], L[i], R[i])) {
                        L[i] = L[L[i] - 1];
                        ok = true;
                    }
                    if (get(c[R[i]], L[i], R[i])) {
                        R[i] = go[R[i] + 1];
                        ok = true;
                    }
                    if (!ok)
                        break;
                }
            }
        } else {
            L[i] = 0;
            R[i] = go[i];
        }
    }
    int q; cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        x--, y--;
        if (L[x] <= y && y <= R[x]) 
            cout << "YES" << '\n';
        else 
            cout << "NO" << '\n';
    }
    return 0;
}

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