oj.uz

Submission #241688

# Submission time Handle Problem Language Result Execution time Memory
241688 2020-06-25T09:13:51 Z osaaateiasavtnl Long Mansion (JOI17_long_mansion) C++17
25 / 100
 3000 ms 51888 KB 
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 1 << 20;
int last[N]; 

int l[N << 2], r[N << 2];
void upd(int v, int tl, int tr, int ql, int qr) {
    if (tr < ql || qr < tl) {
        return;
    }   
    if (ql <= tl && tr <= qr) {
        l[v] = max(l[v], ql);
        r[v] = min(r[v], qr);
        return;
    }   
    int tm = (tl + tr) >> 1;
    upd(v * 2 + 1, tl, tm, ql, qr);
    upd(v * 2 + 2, tm + 1, tr, ql, qr);
}   
void write(int v, int tl, int tr, vector <int> &al, vector <int> &ar) {
    if (tl == tr) {
        al[tl] = l[v];
        ar[tl] = r[v];
        return;
    }   
    int tm = (tl + tr) >> 1;

    l[v * 2 + 1] = max(l[v * 2 + 1], l[v]);
    l[v * 2 + 2] = max(l[v * 2 + 2], l[v]);

    r[v * 2 + 1] = min(r[v * 2 + 1], r[v]);
    r[v * 2 + 2] = min(r[v * 2 + 2], r[v]);

    write(v * 2 + 1, tl, tm, al, ar);
    write(v * 2 + 2, tm + 1, tr, al, ar);
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n;
    cin >> n;

    for (int i = 0; i < (N << 2); ++i)
        r[i] = n - 1;

    vector <int> c(n-1);
    for (int i = 0; i < n - 1; ++i)
        cin >> c[i];

    vector <vector <int> > a(n);
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        a[i].resize(k);
        for (int j = 0; j < k; ++j)
            cin >> a[i][j];
    }   

    vector <int> l(n), r(n);
    for (int i = 0; i < n; ++i) {
        l[i] = 0;
        r[i] = n - 1;
    }   

    vector <int> linkl(n), linkr(n);
    for (int i = 0; i < N; ++i)
        last[i] = -1;
    for (int i = 0; i < n - 1; ++i) {
        for (auto e : a[i])
            last[e] = i;
        linkl[i] = last[c[i]]+1;
    }   
    for (int i = 0; i < N; ++i)
        last[i] = n;
    for (int i = n - 1; i >= 0; --i) {
        if (i < n - 1) {
            linkr[i] = last[c[i]]-1;
        }
        for (auto e : a[i])
            last[e] = i;
    }

    for (int i = 0; i < n - 1; ++i) {
        //(i+1,linkr[i])
        for (int j = i; j <= linkr[i]; ++j) {
            if (linkl[j] <= i+1) {
                int sl = i+1;
                int sr = j;
                upd(0, 0, n - 1, sl, sr);
            }   
        }   
    }   

    for (int i = 0; i < n; ++i) {
        if (linkl[i] == 0) {
            upd(0, 0, n - 1, 0, i);
        }   
    }

    write(0, 0, n - 1, l, r);

    int q;
    cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        --i; --j;
        if (l[i] <= j && j <= r[i]) {
            cout << "YES" << endl;
        }   
        else {
            cout << "NO" << endl;
        }   
    }   
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21120 KB Output is correct
2 Correct 20 ms 21248 KB Output is correct
3 Correct 20 ms 21376 KB Output is correct
4 Correct 19 ms 21120 KB Output is correct
5 Correct 19 ms 21120 KB Output is correct
6 Correct 19 ms 21120 KB Output is correct
7 Correct 86 ms 21092 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21120 KB Output is correct
2 Correct 20 ms 21248 KB Output is correct
3 Correct 20 ms 21376 KB Output is correct
4 Correct 19 ms 21120 KB Output is correct
5 Correct 19 ms 21120 KB Output is correct
6 Correct 19 ms 21120 KB Output is correct
7 Correct 86 ms 21092 KB Output is correct
8 Correct 135 ms 23160 KB Output is correct
9 Correct 143 ms 23032 KB Output is correct
10 Correct 136 ms 23192 KB Output is correct
11 Correct 136 ms 23544 KB Output is correct
12 Correct 121 ms 23160 KB Output is correct
13 Correct 133 ms 23416 KB Output is correct
14 Correct 127 ms 23288 KB Output is correct
15 Correct 135 ms 23364 KB Output is correct
16 Correct 122 ms 23544 KB Output is correct
17 Correct 124 ms 23160 KB Output is correct
18 Correct 127 ms 23160 KB Output is correct
19 Correct 134 ms 23288 KB Output is correct
20 Correct 123 ms 23416 KB Output is correct
21 Correct 126 ms 23416 KB Output is correct
22 Correct 131 ms 23416 KB Output is correct
23 Correct 195 ms 23036 KB Output is correct
24 Correct 207 ms 23116 KB Output is correct
25 Correct 193 ms 23060 KB Output is correct
26 Correct 217 ms 23056 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 31824 KB Output is correct
2 Correct 233 ms 31540 KB Output is correct
3 Correct 223 ms 31584 KB Output is correct
4 Correct 236 ms 31484 KB Output is correct
5 Correct 238 ms 31596 KB Output is correct
6 Correct 199 ms 31640 KB Output is correct
7 Correct 194 ms 31864 KB Output is correct
8 Correct 195 ms 31736 KB Output is correct
9 Correct 197 ms 31864 KB Output is correct
10 Correct 195 ms 31712 KB Output is correct
11 Correct 199 ms 31736 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21120 KB Output is correct
2 Correct 20 ms 21248 KB Output is correct
3 Correct 20 ms 21376 KB Output is correct
4 Correct 19 ms 21120 KB Output is correct
5 Correct 19 ms 21120 KB Output is correct
6 Correct 19 ms 21120 KB Output is correct
7 Correct 86 ms 21092 KB Output is correct
8 Correct 135 ms 23160 KB Output is correct
9 Correct 143 ms 23032 KB Output is correct
10 Correct 136 ms 23192 KB Output is correct
11 Correct 136 ms 23544 KB Output is correct
12 Correct 121 ms 23160 KB Output is correct
13 Correct 133 ms 23416 KB Output is correct
14 Correct 127 ms 23288 KB Output is correct
15 Correct 135 ms 23364 KB Output is correct
16 Correct 122 ms 23544 KB Output is correct
17 Correct 124 ms 23160 KB Output is correct
18 Correct 127 ms 23160 KB Output is correct
19 Correct 134 ms 23288 KB Output is correct
20 Correct 123 ms 23416 KB Output is correct
21 Correct 126 ms 23416 KB Output is correct
22 Correct 131 ms 23416 KB Output is correct
23 Correct 195 ms 23036 KB Output is correct
24 Correct 207 ms 23116 KB Output is correct
25 Correct 193 ms 23060 KB Output is correct
26 Correct 217 ms 23056 KB Output is correct
27 Correct 247 ms 31824 KB Output is correct
28 Correct 233 ms 31540 KB Output is correct
29 Correct 223 ms 31584 KB Output is correct
30 Correct 236 ms 31484 KB Output is correct
31 Correct 238 ms 31596 KB Output is correct
32 Correct 199 ms 31640 KB Output is correct
33 Correct 194 ms 31864 KB Output is correct
34 Correct 195 ms 31736 KB Output is correct
35 Correct 197 ms 31864 KB Output is correct
36 Correct 195 ms 31712 KB Output is correct
37 Correct 199 ms 31736 KB Output is correct
38 Execution timed out 3073 ms 51888 KB Time limit exceeded
39 Halted 0 ms 0 KB -