Submission #334708

#	Time	Username	Problem	Language	Result	Execution time	Memory
334708		12tqian	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1428 ms	96960 KiB

long_mansion

#include <bits/stdc++.h>
const int INF = 1e9;

template <class T> struct MinSegTree {
    const T ID = INF;
    T comb(T a, T b) {
        return std::min(a, b);
    }
    int n;
    std::vector<T> seg;
    void init(int _n) {
        n = _n;
        seg.assign(2 * n, ID);
    }
    void pull(int p) {
        seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
    }
    void upd(int p, T val) {
        seg[p += n] = val;
        for (p /= 2; p; p /= 2) pull(p);
    }
    void add(int p, T val) {
        seg[p += n] += val;
        for (p /= 2; p; p /= 2) pull(p);
    }
    T query(int l, int r) {
        if (l > r) return ID;
        T ra = ID, rb = ID;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l & 1) ra = comb(ra, seg[l++]);
            if (r & 1) rb = comb(seg[--r], rb);
        }
        return comb(ra, rb);
    }
};


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]--;
    }

    int q; cin >> q;
    vector<array<int, 2>> queries(q);
    for (int i = 0 ; i< q; i++) {
        cin >> queries[i][0] >> queries[i][1];
        queries[i][0]--, queries[i][1]--;
    }

    vector<int> ans(q);

    auto solve = [&]() {
        vector<int> L(n), R(n);
        vector<vector<int>> loc(n);
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < b[i]; j++) 
                loc[a[i][j]].push_back(i);

        L.back() = -1;
        R.back() = n;

        for (int i = 0; i < n - 1; i++) {
            auto it = lower_bound(loc[c[i]].begin(), loc[c[i]].end(), i + 1);
            if (it == loc[c[i]].end()) R[i] = n;
            else R[i] = *it;

            it = upper_bound(loc[c[i]].begin(), loc[c[i]].end(), i);
            if (it == loc[c[i]].begin()) L[i] = -1;
            else L[i] = *prev(it);
        }

        vector<int> go_left(n);
        vector<vector<int>> rem(n);

        for (int i = 0; i < n; i++) {
            int right = n;
            if (i) right = R[i - 1];
            if (right < n) rem[right].push_back(i);
        }

        MinSegTree<int> mst;
        mst.init(n);
        
        for (int i = 0; i < n; i++)
            mst.upd(i, n);

        for (int i = 0; i < n; i++) {
            mst.upd(i, i);
            for (int r : rem[i]) 
                mst.upd(r, n);
            go_left[i] = mst.query(L[i] + 1, i);
        }  

        MinSegTree<int> seg;
        seg.init(n);

        for (int i = 0; i < n; i++)
            seg.upd(i, go_left[i]);
        for (int i = 0; i < q; i++) {
            if (queries[i][0] < queries[i][1]) {
                int l = queries[i][0];
                int r = queries[i][1];
                if (seg.query(l, r - 1) <= l) 
                    ans[i] = 0;
                else 
                    ans[i] = 1;
            }
        }
    };

    solve();

    reverse(a.begin(), a.end());
    c.pop_back();
    reverse(c.begin(), c.end());
    c.push_back(-1);
    reverse(b.begin(), b.end());

    for (int i = 0; i < q; i++) {
        queries[i][0] = n - 1 - queries[i][0];
        queries[i][1] = n - 1 - queries[i][1];
    }

    solve();

    for (int i = 0; i < q; i++)
        cout << (ans[i] ? "YES" : "NO") << '\n';
    return 0;
}

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