oj.uz

Submission #334708

# Submission time Handle Problem Language Result Execution time Memory
334708 2020-12-09T20:53:04 Z 12tqian Long Mansion (JOI17_long_mansion) C++17
100 / 100
 1428 ms 96960 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Output is correct
2 Correct 9 ms 932 KB Output is correct
3 Correct 11 ms 1344 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 7 ms 876 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Output is correct
2 Correct 9 ms 932 KB Output is correct
3 Correct 11 ms 1344 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 7 ms 876 KB Output is correct
8 Correct 358 ms 8516 KB Output is correct
9 Correct 401 ms 8536 KB Output is correct
10 Correct 371 ms 8940 KB Output is correct
11 Correct 376 ms 9168 KB Output is correct
12 Correct 345 ms 8556 KB Output is correct
13 Correct 320 ms 8684 KB Output is correct
14 Correct 328 ms 8684 KB Output is correct
15 Correct 331 ms 8812 KB Output is correct
16 Correct 327 ms 9196 KB Output is correct
17 Correct 323 ms 8684 KB Output is correct
18 Correct 329 ms 8684 KB Output is correct
19 Correct 345 ms 8812 KB Output is correct
20 Correct 330 ms 8940 KB Output is correct
21 Correct 329 ms 8940 KB Output is correct
22 Correct 340 ms 8812 KB Output is correct
23 Correct 314 ms 8556 KB Output is correct
24 Correct 316 ms 8556 KB Output is correct
25 Correct 313 ms 8556 KB Output is correct
26 Correct 311 ms 8668 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 26044 KB Output is correct
2 Correct 656 ms 32704 KB Output is correct
3 Correct 646 ms 32992 KB Output is correct
4 Correct 670 ms 33040 KB Output is correct
5 Correct 664 ms 31212 KB Output is correct
6 Correct 551 ms 30304 KB Output is correct
7 Correct 553 ms 32084 KB Output is correct
8 Correct 560 ms 30292 KB Output is correct
9 Correct 553 ms 30164 KB Output is correct
10 Correct 553 ms 30292 KB Output is correct
11 Correct 550 ms 30292 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Output is correct
2 Correct 9 ms 932 KB Output is correct
3 Correct 11 ms 1344 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 7 ms 876 KB Output is correct
8 Correct 358 ms 8516 KB Output is correct
9 Correct 401 ms 8536 KB Output is correct
10 Correct 371 ms 8940 KB Output is correct
11 Correct 376 ms 9168 KB Output is correct
12 Correct 345 ms 8556 KB Output is correct
13 Correct 320 ms 8684 KB Output is correct
14 Correct 328 ms 8684 KB Output is correct
15 Correct 331 ms 8812 KB Output is correct
16 Correct 327 ms 9196 KB Output is correct
17 Correct 323 ms 8684 KB Output is correct
18 Correct 329 ms 8684 KB Output is correct
19 Correct 345 ms 8812 KB Output is correct
20 Correct 330 ms 8940 KB Output is correct
21 Correct 329 ms 8940 KB Output is correct
22 Correct 340 ms 8812 KB Output is correct
23 Correct 314 ms 8556 KB Output is correct
24 Correct 316 ms 8556 KB Output is correct
25 Correct 313 ms 8556 KB Output is correct
26 Correct 311 ms 8668 KB Output is correct
27 Correct 668 ms 26044 KB Output is correct
28 Correct 656 ms 32704 KB Output is correct
29 Correct 646 ms 32992 KB Output is correct
30 Correct 670 ms 33040 KB Output is correct
31 Correct 664 ms 31212 KB Output is correct
32 Correct 551 ms 30304 KB Output is correct
33 Correct 553 ms 32084 KB Output is correct
34 Correct 560 ms 30292 KB Output is correct
35 Correct 553 ms 30164 KB Output is correct
36 Correct 553 ms 30292 KB Output is correct
37 Correct 550 ms 30292 KB Output is correct
38 Correct 1332 ms 83532 KB Output is correct
39 Correct 1428 ms 96888 KB Output is correct
40 Correct 1115 ms 65660 KB Output is correct
41 Correct 1280 ms 96960 KB Output is correct
42 Correct 565 ms 31724 KB Output is correct
43 Correct 571 ms 31724 KB Output is correct
44 Correct 845 ms 53100 KB Output is correct
45 Correct 855 ms 53484 KB Output is correct
46 Correct 880 ms 54364 KB Output is correct
47 Correct 610 ms 32236 KB Output is correct
48 Correct 590 ms 31596 KB Output is correct
49 Correct 860 ms 52632 KB Output is correct
50 Correct 877 ms 53304 KB Output is correct
51 Correct 927 ms 54824 KB Output is correct
52 Correct 727 ms 53696 KB Output is correct
53 Correct 918 ms 73948 KB Output is correct
54 Correct 1109 ms 93896 KB Output is correct
55 Correct 921 ms 73588 KB Output is correct