oj.uz

Submission #334705

# Submission time Handle Problem Language Result Execution time Memory
334705 2020-12-09T20:41:43 Z 12tqian Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 18796 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;
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    // 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);

        for (int i = 0; i < n; i++) {
            go_left[i] = n;
            for (int j = i; j >= 0; j--) {
                int val;
                if (j) val = R[j - 1];
                else val = n;
                if (L[i] < j && i < val) {
                    go_left[i] = j;
                }
            }
        }
        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 11 ms 748 KB Output is correct
2 Correct 16 ms 876 KB Output is correct
3 Correct 33 ms 1004 KB Output is correct
4 Correct 11 ms 748 KB Output is correct
5 Correct 10 ms 748 KB Output is correct
6 Correct 11 ms 748 KB Output is correct
7 Correct 11 ms 748 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 748 KB Output is correct
2 Correct 16 ms 876 KB Output is correct
3 Correct 33 ms 1004 KB Output is correct
4 Correct 11 ms 748 KB Output is correct
5 Correct 10 ms 748 KB Output is correct
6 Correct 11 ms 748 KB Output is correct
7 Correct 11 ms 748 KB Output is correct
8 Correct 355 ms 8300 KB Output is correct
9 Correct 358 ms 8300 KB Output is correct
10 Correct 368 ms 8556 KB Output is correct
11 Correct 393 ms 8812 KB Output is correct
12 Correct 331 ms 8428 KB Output is correct
13 Correct 332 ms 8428 KB Output is correct
14 Correct 327 ms 8536 KB Output is correct
15 Correct 329 ms 8556 KB Output is correct
16 Correct 321 ms 8684 KB Output is correct
17 Correct 319 ms 8428 KB Output is correct
18 Correct 325 ms 8428 KB Output is correct
19 Correct 338 ms 8556 KB Output is correct
20 Correct 334 ms 8684 KB Output is correct
21 Correct 326 ms 8812 KB Output is correct
22 Correct 334 ms 8428 KB Output is correct
23 Correct 318 ms 8300 KB Output is correct
24 Correct 317 ms 8300 KB Output is correct
25 Correct 316 ms 8300 KB Output is correct
26 Correct 317 ms 8380 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 18796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 748 KB Output is correct
2 Correct 16 ms 876 KB Output is correct
3 Correct 33 ms 1004 KB Output is correct
4 Correct 11 ms 748 KB Output is correct
5 Correct 10 ms 748 KB Output is correct
6 Correct 11 ms 748 KB Output is correct
7 Correct 11 ms 748 KB Output is correct
8 Correct 355 ms 8300 KB Output is correct
9 Correct 358 ms 8300 KB Output is correct
10 Correct 368 ms 8556 KB Output is correct
11 Correct 393 ms 8812 KB Output is correct
12 Correct 331 ms 8428 KB Output is correct
13 Correct 332 ms 8428 KB Output is correct
14 Correct 327 ms 8536 KB Output is correct
15 Correct 329 ms 8556 KB Output is correct
16 Correct 321 ms 8684 KB Output is correct
17 Correct 319 ms 8428 KB Output is correct
18 Correct 325 ms 8428 KB Output is correct
19 Correct 338 ms 8556 KB Output is correct
20 Correct 334 ms 8684 KB Output is correct
21 Correct 326 ms 8812 KB Output is correct
22 Correct 334 ms 8428 KB Output is correct
23 Correct 318 ms 8300 KB Output is correct
24 Correct 317 ms 8300 KB Output is correct
25 Correct 316 ms 8300 KB Output is correct
26 Correct 317 ms 8380 KB Output is correct
27 Execution timed out 3058 ms 18796 KB Time limit exceeded
28 Halted 0 ms 0 KB -