oj.uz

Submission #1096961

# Submission time Handle Problem Language Result Execution time Memory
1096961 2024-10-05T15:03:15 Z vladilius Long Mansion (JOI17_long_mansion) C++17
25 / 100
 3000 ms 125264 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]);
    }
    
    map<pii, pii> mp;
    function<pii(int, int)> solve = [&](int l, int r){
        int l1 = l, r1 = r;
        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){
            mp[{l, r}] = {l, r};
            return make_pair(l, r);
        }
        pii x = solve(l, r);
        mp[{l1, r1}] = x;
        return x;
    };

    vector<pii> rr(n + 1);
    for (int i = 1; i <= n; i++){
        solve(i, i);
        rr[i] = mp[{i, i}];
    }
    
    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 856 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 5 ms 1560 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 52 ms 992 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 5 ms 1560 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 52 ms 992 KB Output is correct
8 Correct 67 ms 6700 KB Output is correct
9 Correct 73 ms 6644 KB Output is correct
10 Correct 66 ms 7252 KB Output is correct
11 Correct 67 ms 8016 KB Output is correct
12 Correct 60 ms 6228 KB Output is correct
13 Correct 60 ms 6740 KB Output is correct
14 Correct 75 ms 6740 KB Output is correct
15 Correct 63 ms 6792 KB Output is correct
16 Correct 65 ms 6544 KB Output is correct
17 Correct 61 ms 6744 KB Output is correct
18 Correct 67 ms 6936 KB Output is correct
19 Correct 75 ms 6736 KB Output is correct
20 Correct 64 ms 6784 KB Output is correct
21 Correct 66 ms 6740 KB Output is correct
22 Correct 63 ms 6704 KB Output is correct
23 Correct 101 ms 6636 KB Output is correct
24 Correct 107 ms 6744 KB Output is correct
25 Correct 122 ms 6664 KB Output is correct
26 Correct 95 ms 6704 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 33360 KB Output is correct
2 Correct 164 ms 33356 KB Output is correct
3 Correct 152 ms 32872 KB Output is correct
4 Correct 152 ms 33364 KB Output is correct
5 Correct 168 ms 33364 KB Output is correct
6 Correct 153 ms 31312 KB Output is correct
7 Correct 149 ms 30032 KB Output is correct
8 Correct 144 ms 29776 KB Output is correct
9 Correct 143 ms 29776 KB Output is correct
10 Correct 152 ms 29536 KB Output is correct
11 Correct 160 ms 29500 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 5 ms 1560 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 52 ms 992 KB Output is correct
8 Correct 67 ms 6700 KB Output is correct
9 Correct 73 ms 6644 KB Output is correct
10 Correct 66 ms 7252 KB Output is correct
11 Correct 67 ms 8016 KB Output is correct
12 Correct 60 ms 6228 KB Output is correct
13 Correct 60 ms 6740 KB Output is correct
14 Correct 75 ms 6740 KB Output is correct
15 Correct 63 ms 6792 KB Output is correct
16 Correct 65 ms 6544 KB Output is correct
17 Correct 61 ms 6744 KB Output is correct
18 Correct 67 ms 6936 KB Output is correct
19 Correct 75 ms 6736 KB Output is correct
20 Correct 64 ms 6784 KB Output is correct
21 Correct 66 ms 6740 KB Output is correct
22 Correct 63 ms 6704 KB Output is correct
23 Correct 101 ms 6636 KB Output is correct
24 Correct 107 ms 6744 KB Output is correct
25 Correct 122 ms 6664 KB Output is correct
26 Correct 95 ms 6704 KB Output is correct
27 Correct 165 ms 33360 KB Output is correct
28 Correct 164 ms 33356 KB Output is correct
29 Correct 152 ms 32872 KB Output is correct
30 Correct 152 ms 33364 KB Output is correct
31 Correct 168 ms 33364 KB Output is correct
32 Correct 153 ms 31312 KB Output is correct
33 Correct 149 ms 30032 KB Output is correct
34 Correct 144 ms 29776 KB Output is correct
35 Correct 143 ms 29776 KB Output is correct
36 Correct 152 ms 29536 KB Output is correct
37 Correct 160 ms 29500 KB Output is correct
38 Correct 382 ms 98008 KB Output is correct
39 Correct 466 ms 118864 KB Output is correct
40 Correct 309 ms 75860 KB Output is correct
41 Correct 545 ms 125264 KB Output is correct
42 Correct 166 ms 32592 KB Output is correct
43 Correct 162 ms 31564 KB Output is correct
44 Correct 274 ms 55372 KB Output is correct
45 Correct 275 ms 55120 KB Output is correct
46 Correct 285 ms 54840 KB Output is correct
47 Correct 169 ms 30800 KB Output is correct
48 Correct 165 ms 30544 KB Output is correct
49 Correct 277 ms 54356 KB Output is correct
50 Correct 276 ms 54460 KB Output is correct
51 Correct 272 ms 54744 KB Output is correct
52 Execution timed out 3068 ms 54364 KB Time limit exceeded
53 Halted 0 ms 0 KB -