oj.uz

Submission #1096962

# Submission time Handle Problem Language Result Execution time Memory
1096962 2024-10-05T15:04:28 Z vladilius Long Mansion (JOI17_long_mansion) C++17
100 / 100
 627 ms 131700 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){
        auto it = mp.find({l, r});
        if (it != mp.end()) return (*it).ss;
        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 1628 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 2 ms 860 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 1628 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 72 ms 4792 KB Output is correct
9 Correct 71 ms 4948 KB Output is correct
10 Correct 67 ms 5204 KB Output is correct
11 Correct 65 ms 5824 KB Output is correct
12 Correct 59 ms 4304 KB Output is correct
13 Correct 63 ms 4944 KB Output is correct
14 Correct 65 ms 4948 KB Output is correct
15 Correct 63 ms 4944 KB Output is correct
16 Correct 58 ms 4948 KB Output is correct
17 Correct 61 ms 4948 KB Output is correct
18 Correct 59 ms 4944 KB Output is correct
19 Correct 61 ms 5176 KB Output is correct
20 Correct 61 ms 4992 KB Output is correct
21 Correct 62 ms 5000 KB Output is correct
22 Correct 62 ms 4688 KB Output is correct
23 Correct 65 ms 4636 KB Output is correct
24 Correct 65 ms 4724 KB Output is correct
25 Correct 69 ms 4876 KB Output is correct
26 Correct 69 ms 4688 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 29800 KB Output is correct
2 Correct 171 ms 29820 KB Output is correct
3 Correct 173 ms 29744 KB Output is correct
4 Correct 179 ms 29776 KB Output is correct
5 Correct 169 ms 31960 KB Output is correct
6 Correct 165 ms 30292 KB Output is correct
7 Correct 168 ms 28756 KB Output is correct
8 Correct 159 ms 28468 KB Output is correct
9 Correct 156 ms 28496 KB Output is correct
10 Correct 157 ms 28332 KB Output is correct
11 Correct 160 ms 28316 KB Output is correct

Subtask #4
75.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 1628 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 72 ms 4792 KB Output is correct
9 Correct 71 ms 4948 KB Output is correct
10 Correct 67 ms 5204 KB Output is correct
11 Correct 65 ms 5824 KB Output is correct
12 Correct 59 ms 4304 KB Output is correct
13 Correct 63 ms 4944 KB Output is correct
14 Correct 65 ms 4948 KB Output is correct
15 Correct 63 ms 4944 KB Output is correct
16 Correct 58 ms 4948 KB Output is correct
17 Correct 61 ms 4948 KB Output is correct
18 Correct 59 ms 4944 KB Output is correct
19 Correct 61 ms 5176 KB Output is correct
20 Correct 61 ms 4992 KB Output is correct
21 Correct 62 ms 5000 KB Output is correct
22 Correct 62 ms 4688 KB Output is correct
23 Correct 65 ms 4636 KB Output is correct
24 Correct 65 ms 4724 KB Output is correct
25 Correct 69 ms 4876 KB Output is correct
26 Correct 69 ms 4688 KB Output is correct
27 Correct 182 ms 29800 KB Output is correct
28 Correct 171 ms 29820 KB Output is correct
29 Correct 173 ms 29744 KB Output is correct
30 Correct 179 ms 29776 KB Output is correct
31 Correct 169 ms 31960 KB Output is correct
32 Correct 165 ms 30292 KB Output is correct
33 Correct 168 ms 28756 KB Output is correct
34 Correct 159 ms 28468 KB Output is correct
35 Correct 156 ms 28496 KB Output is correct
36 Correct 157 ms 28332 KB Output is correct
37 Correct 160 ms 28316 KB Output is correct
38 Correct 414 ms 95556 KB Output is correct
39 Correct 510 ms 116608 KB Output is correct
40 Correct 337 ms 73808 KB Output is correct
41 Correct 627 ms 123216 KB Output is correct
42 Correct 175 ms 31312 KB Output is correct
43 Correct 173 ms 30032 KB Output is correct
44 Correct 256 ms 53332 KB Output is correct
45 Correct 255 ms 52944 KB Output is correct
46 Correct 250 ms 52816 KB Output is correct
47 Correct 165 ms 29268 KB Output is correct
48 Correct 153 ms 29272 KB Output is correct
49 Correct 272 ms 52308 KB Output is correct
50 Correct 263 ms 52308 KB Output is correct
51 Correct 311 ms 52484 KB Output is correct
52 Correct 288 ms 67412 KB Output is correct
53 Correct 413 ms 98524 KB Output is correct
54 Correct 527 ms 131700 KB Output is correct
55 Correct 420 ms 98368 KB Output is correct