oj.uz

Submission #1096945

# Submission time Handle Problem Language Result Execution time Memory
1096945 2024-10-05T14:02:24 Z vladilius Long Mansion (JOI17_long_mansion) C++17
25 / 100
 3000 ms 85068 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

struct ST{
    vector<pii> t;
    vector<int> a;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
        a.resize(n + 1);
    }
    void upd(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            t[v] = {x, x};
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, x);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x);
        }
        t[v].ff = min(t[vv].ff, t[vv + 1].ff);
        t[v].ss = max(t[vv].ss, t[vv + 1].ss);
    }
    void upd(int p, int x){
        upd(1, 1, n, p, x);
        a[p] = x;
    }
    vector<arr3> all;
    void dec(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            all.pb({v, tl, tr});
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        dec(vv, tl, tm, l, r);
        dec(vv + 1, tm + 1, tr, l, r);
    }
    int fn1(int v, int tl, int tr, int& x){
        if (tl == tr) return (tl - (a[tl] <= x));
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (t[vv + 1].ss > x){
            return fn1(vv + 1, tm + 1, tr, x);
        }
        return fn1(vv, tl, tm, x);
    }
    int find1(int l, int r, int x){
        if (l > r || a[r] > x) return -1;
        all.clear();
        dec(1, 1, n, l, r);
        reverse(all.begin(), all.end());
        for (auto [v, tl, tr]: all){
            if (t[v].ss > x){
                return fn1(v, tl, tr, x) + 1;
            }
        }
        return l;
    }
    int fn2(int v, int tl, int tr, int& x){
        if (tl == tr) return tl + (a[tl] >= x);
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (t[vv].ff < x){
            return fn2(vv, tl, tm, x);
        }
        return fn2(vv + 1, tm + 1, tr, x);
    }
    int find2(int l, int r, int x){
        if (l > r || a[l] < x) return -1;
        all.clear();
        dec(1, 1, n, l, r);
        for (auto [v, tl, tr]: all){
            if (t[v].ff < x){
                return fn2(v, tl, tr, x) - 1;
            }
        }
        return r;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> c(n);
    for (int i = 1; i < n; i++){
        cin>>c[i];
    }
    
    vector<int> A[n + 1];
    for (int i = 1; i <= n; i++){
        int x; cin>>x;
        while (x--){
            int y; cin>>y;
            A[i].pb(y);
        }
    }
    
    vector<int> x(n), lst(n + 1, n + 1);
    for (int i = n; i > 0; i--){
        if (i < n){
            x[i] = lst[c[i]];
        }
        for (int j: A[i]){
            lst[j] = i;
        }
    }
    
    fill(lst.begin(), lst.end(), 0);
    vector<int> y(n);
    for (int i = 1; i < n; i++){
        for (int j: A[i]){
            lst[j] = i;
        }
        y[i] = lst[c[i]];
    }
    
    ST T1(n - 1), T2(n - 1);
    for (int i = 1; i < n; i++){
        T1.upd(i, x[i]);
        T2.upd(i, y[i]);
    }

    vector<pii> rr(n + 1);
    for (int i = 1; i <= n; i++){
        int l = i, r = i;
        while (true){
            bool ind1 = 0, ind2 = 0;
            int j = T1.find1(1, l - 1, r);
            if (j != -1){
                l = j;
                ind1 = 1;
            }
            j = T2.find2(r, n - 1, l);
            if (j != -1){
                r = j + 1;
                ind2 = 1;
            }
            if (!ind1 && !ind2) break;
        }
        rr[i] = {l, r};
    }
    
    int Q; cin>>Q;
    while (Q--){
        int x, y; cin>>x>>y;
        cout<<((rr[x].ff <= y && y <= rr[x].ss) ? "YES" : "NO")<<"\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 608 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 34 ms 812 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 608 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 34 ms 812 KB Output is correct
8 Correct 66 ms 5968 KB Output is correct
9 Correct 68 ms 5968 KB Output is correct
10 Correct 64 ms 6160 KB Output is correct
11 Correct 73 ms 6664 KB Output is correct
12 Correct 66 ms 5264 KB Output is correct
13 Correct 68 ms 6108 KB Output is correct
14 Correct 93 ms 6188 KB Output is correct
15 Correct 61 ms 5956 KB Output is correct
16 Correct 60 ms 5972 KB Output is correct
17 Correct 67 ms 6224 KB Output is correct
18 Correct 72 ms 6224 KB Output is correct
19 Correct 108 ms 6316 KB Output is correct
20 Correct 59 ms 6044 KB Output is correct
21 Correct 58 ms 6012 KB Output is correct
22 Correct 58 ms 5924 KB Output is correct
23 Correct 89 ms 5748 KB Output is correct
24 Correct 91 ms 5712 KB Output is correct
25 Correct 141 ms 5716 KB Output is correct
26 Correct 81 ms 5716 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 23504 KB Output is correct
2 Correct 143 ms 23380 KB Output is correct
3 Correct 139 ms 23008 KB Output is correct
4 Correct 146 ms 23376 KB Output is correct
5 Correct 150 ms 23488 KB Output is correct
6 Correct 216 ms 22284 KB Output is correct
7 Correct 132 ms 22012 KB Output is correct
8 Correct 134 ms 21948 KB Output is correct
9 Correct 137 ms 22148 KB Output is correct
10 Correct 135 ms 21996 KB Output is correct
11 Correct 145 ms 22100 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 608 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 34 ms 812 KB Output is correct
8 Correct 66 ms 5968 KB Output is correct
9 Correct 68 ms 5968 KB Output is correct
10 Correct 64 ms 6160 KB Output is correct
11 Correct 73 ms 6664 KB Output is correct
12 Correct 66 ms 5264 KB Output is correct
13 Correct 68 ms 6108 KB Output is correct
14 Correct 93 ms 6188 KB Output is correct
15 Correct 61 ms 5956 KB Output is correct
16 Correct 60 ms 5972 KB Output is correct
17 Correct 67 ms 6224 KB Output is correct
18 Correct 72 ms 6224 KB Output is correct
19 Correct 108 ms 6316 KB Output is correct
20 Correct 59 ms 6044 KB Output is correct
21 Correct 58 ms 6012 KB Output is correct
22 Correct 58 ms 5924 KB Output is correct
23 Correct 89 ms 5748 KB Output is correct
24 Correct 91 ms 5712 KB Output is correct
25 Correct 141 ms 5716 KB Output is correct
26 Correct 81 ms 5716 KB Output is correct
27 Correct 145 ms 23504 KB Output is correct
28 Correct 143 ms 23380 KB Output is correct
29 Correct 139 ms 23008 KB Output is correct
30 Correct 146 ms 23376 KB Output is correct
31 Correct 150 ms 23488 KB Output is correct
32 Correct 216 ms 22284 KB Output is correct
33 Correct 132 ms 22012 KB Output is correct
34 Correct 134 ms 21948 KB Output is correct
35 Correct 137 ms 22148 KB Output is correct
36 Correct 135 ms 21996 KB Output is correct
37 Correct 145 ms 22100 KB Output is correct
38 Correct 253 ms 70576 KB Output is correct
39 Correct 282 ms 85068 KB Output is correct
40 Correct 219 ms 54860 KB Output is correct
41 Correct 350 ms 84160 KB Output is correct
42 Correct 127 ms 23124 KB Output is correct
43 Correct 133 ms 23084 KB Output is correct
44 Correct 208 ms 39760 KB Output is correct
45 Correct 208 ms 39696 KB Output is correct
46 Correct 222 ms 39944 KB Output is correct
47 Correct 140 ms 22820 KB Output is correct
48 Correct 152 ms 22868 KB Output is correct
49 Correct 214 ms 39760 KB Output is correct
50 Correct 224 ms 39764 KB Output is correct
51 Correct 219 ms 40036 KB Output is correct
52 Execution timed out 3066 ms 32852 KB Time limit exceeded
53 Halted 0 ms 0 KB -