oj.uz

Submission #241698

# Submission time Handle Problem Language Result Execution time Memory
241698 2020-06-25T09:36:45 Z osaaateiasavtnl Long Mansion (JOI17_long_mansion) C++17
25 / 100
 3000 ms 68888 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);
}   

void build(int v, int tl, int tr, vector <int> &a, int tree[N << 2], bool (*comp)(int , int)) {
    if (tl == tr) {
        tree[v] = a[tl];
        return;
    }   
    int tm = (tl + tr) >> 1;
    build(v * 2 + 1, tl, tm, a, tree, comp);
    build(v * 2 + 2, tm + 1, tr, a, tree, comp);
    if (comp(tree[v * 2 + 1], tree[v * 2 + 2]))
        tree[v] = tree[v * 2 + 1];
    else
        tree[v] = tree[v * 2 + 2];
}   
int getl(int v, int tl, int tr, int l, int r, int x, int tree[N << 2], bool (*comp)(int, int)) {
    if (comp(x, tree[v]) || r < tl || tr < l)
        return -1;
    if (tl == tr)
        return tl;
    int tm = (tl + tr) >> 1;
    int t = getl(v * 2 + 1, tl, tm, l, r, x, tree, comp);
    if (t != -1)
        return t;
    else
        return getl(v * 2 + 2, tm + 1, tr, l, r, x, tree, comp);
}   
int getr(int v, int tl, int tr, int l, int r, int x, int tree[N << 2], bool (*comp)(int, int)) {
    if (comp(x, tree[v]) || r < tl || tr < l)
        return -1;
    if (tl == tr)
        return tl;
    int tm = (tl + tr) >> 1;
    int t = getr(v * 2 + 2, tm + 1, tr, l, r, x, tree, comp);
    if (t != -1)
        return t;
    else
        return getr(v * 2 + 1, tl, tm, l, r, x, tree, comp);
}   

bool ls(int a, int b) { return a < b; }
bool bg(int a, int b) { return a > b; }

int mn[N << 2], mx[N << 2];

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

    build(0, 0, n - 1, linkl, mn, ls);
    for (int i = 0; i < n; ++i) {
        int j = getr(0, 0, n - 1, i, linkr[i], i+1, mn, ls);
        if (j != -1) {
            upd(0, 0, n - 1, i+1, j);
        }   
    }   
    for (int j = 0; j < n; ++j) {
        for (int i = linkl[j]-1; i <= j; ++i) {
            if (j <= linkr[i]) {
                upd(0, 0, n - 1, i+1, j);    
                break;
            }
        }   
    }   

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

    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 20 ms 21120 KB Output is correct
2 Correct 19 ms 21248 KB Output is correct
3 Correct 20 ms 21504 KB Output is correct
4 Correct 20 ms 21120 KB Output is correct
5 Correct 20 ms 21120 KB Output is correct
6 Correct 19 ms 21120 KB Output is correct
7 Correct 21 ms 21200 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21120 KB Output is correct
2 Correct 19 ms 21248 KB Output is correct
3 Correct 20 ms 21504 KB Output is correct
4 Correct 20 ms 21120 KB Output is correct
5 Correct 20 ms 21120 KB Output is correct
6 Correct 19 ms 21120 KB Output is correct
7 Correct 21 ms 21200 KB Output is correct
8 Correct 143 ms 24312 KB Output is correct
9 Correct 139 ms 24184 KB Output is correct
10 Correct 143 ms 24568 KB Output is correct
11 Correct 136 ms 24824 KB Output is correct
12 Correct 126 ms 24440 KB Output is correct
13 Correct 136 ms 24568 KB Output is correct
14 Correct 129 ms 24440 KB Output is correct
15 Correct 133 ms 24696 KB Output is correct
16 Correct 130 ms 24868 KB Output is correct
17 Correct 131 ms 24504 KB Output is correct
18 Correct 140 ms 24680 KB Output is correct
19 Correct 126 ms 24440 KB Output is correct
20 Correct 134 ms 24696 KB Output is correct
21 Correct 124 ms 24696 KB Output is correct
22 Correct 126 ms 24440 KB Output is correct
23 Correct 142 ms 24312 KB Output is correct
24 Correct 139 ms 24312 KB Output is correct
25 Correct 132 ms 24312 KB Output is correct
26 Correct 140 ms 24312 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 33792 KB Output is correct
2 Correct 256 ms 33852 KB Output is correct
3 Correct 258 ms 33912 KB Output is correct
4 Correct 262 ms 33784 KB Output is correct
5 Correct 258 ms 33784 KB Output is correct
6 Correct 238 ms 33912 KB Output is correct
7 Correct 227 ms 34040 KB Output is correct
8 Correct 225 ms 34040 KB Output is correct
9 Correct 225 ms 34040 KB Output is correct
10 Correct 227 ms 34044 KB Output is correct
11 Correct 226 ms 34084 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21120 KB Output is correct
2 Correct 19 ms 21248 KB Output is correct
3 Correct 20 ms 21504 KB Output is correct
4 Correct 20 ms 21120 KB Output is correct
5 Correct 20 ms 21120 KB Output is correct
6 Correct 19 ms 21120 KB Output is correct
7 Correct 21 ms 21200 KB Output is correct
8 Correct 143 ms 24312 KB Output is correct
9 Correct 139 ms 24184 KB Output is correct
10 Correct 143 ms 24568 KB Output is correct
11 Correct 136 ms 24824 KB Output is correct
12 Correct 126 ms 24440 KB Output is correct
13 Correct 136 ms 24568 KB Output is correct
14 Correct 129 ms 24440 KB Output is correct
15 Correct 133 ms 24696 KB Output is correct
16 Correct 130 ms 24868 KB Output is correct
17 Correct 131 ms 24504 KB Output is correct
18 Correct 140 ms 24680 KB Output is correct
19 Correct 126 ms 24440 KB Output is correct
20 Correct 134 ms 24696 KB Output is correct
21 Correct 124 ms 24696 KB Output is correct
22 Correct 126 ms 24440 KB Output is correct
23 Correct 142 ms 24312 KB Output is correct
24 Correct 139 ms 24312 KB Output is correct
25 Correct 132 ms 24312 KB Output is correct
26 Correct 140 ms 24312 KB Output is correct
27 Correct 257 ms 33792 KB Output is correct
28 Correct 256 ms 33852 KB Output is correct
29 Correct 258 ms 33912 KB Output is correct
30 Correct 262 ms 33784 KB Output is correct
31 Correct 258 ms 33784 KB Output is correct
32 Correct 238 ms 33912 KB Output is correct
33 Correct 227 ms 34040 KB Output is correct
34 Correct 225 ms 34040 KB Output is correct
35 Correct 225 ms 34040 KB Output is correct
36 Correct 227 ms 34044 KB Output is correct
37 Correct 226 ms 34084 KB Output is correct
38 Correct 648 ms 62040 KB Output is correct
39 Correct 720 ms 68660 KB Output is correct
40 Correct 517 ms 53752 KB Output is correct
41 Correct 546 ms 68888 KB Output is correct
42 Correct 252 ms 32888 KB Output is correct
43 Correct 246 ms 32888 KB Output is correct
44 Correct 351 ms 42360 KB Output is correct
45 Correct 350 ms 42488 KB Output is correct
46 Correct 354 ms 42484 KB Output is correct
47 Correct 248 ms 32892 KB Output is correct
48 Correct 243 ms 32840 KB Output is correct
49 Correct 335 ms 42360 KB Output is correct
50 Correct 337 ms 42316 KB Output is correct
51 Correct 338 ms 42104 KB Output is correct
52 Execution timed out 3082 ms 40184 KB Time limit exceeded
53 Halted 0 ms 0 KB -