oj.uz

Submission #824631

# Submission time Handle Problem Language Result Execution time Memory
824631 2023-08-14T08:24:46 Z dimashhh Birthday gift (IZhO18_treearray) C++17
56 / 100
 359 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 1,MOD = 998244353;

int n,m,q,a[N],up[N][25],tin[N],tout[N],timer = 0,b[N];
vector<int> g[N];
multiset<pair<int,int>> s[N * 4],t[N * 4];
pair<int,int> cur,cur1;

void dfs(int v,int pr = 1){
    tin[v] = ++timer;
    up[v][0] = pr;
    for(int i = 1;i <= 20;i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:g[v]){
        if(to != pr) dfs(to,v);
    }
    tout[v] = timer;
}
bool is(int v,int u){
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int lca(int v,int u){
    if(is(v,u)) return v;
    if(is(u,v)) return u;
    for(int i = 18;i >= 0;i--){
        if(!is(up[v][i],u)){
            v = up[v][i];
        }
    }
    return up[v][0];
}
void build(int v = 1,int tl = 1,int tr = m - 1){
    if(tl == tr){
        s[v].insert(make_pair(b[tl],tl));
    }else{
        int tm = (tl + tr) >> 1;
        build(v + v,tl,tm);
        build(v + v + 1,tm + 1,tr);
        s[v] = s[v + v];
        for(auto k:s[v + v + 1]){
            s[v].insert(k);
        }
   }
}
void build1(int v = 1,int tl = 1,int tr = m){
    if(tl == tr){
        t[v].insert({a[tl],tl});
    }else{
        int tm = (tl + tr) >> 1;
        build1(v + v,tl,tm);
        build1(v + v + 1,tm + 1,tr);
        t[v] = t[v + v];
        for(auto k:t[v + v + 1]){
            t[v].insert(k);
        }
    }
}
void upd1(int pos,int val,int v = 1,int tl = 1,int tr = m){
    t[v].erase({a[pos],pos});
    t[v].insert({val,pos});
    if(tl == tr) return;
    int tm = (tl + tr) >> 1;
    if(pos <= tm) upd1(pos,val,v+v,tl,tm);
    else upd1(pos,val,v+v+1,tm+1,tr);
}
bool find1(int l,int r,int val,int v = 1,int tl = 1,int tr = m){
    if(tl > r || l > tr || l > r) return false;
    if(tl >= l && tr <=r){
        auto it = t[v].lower_bound({val,0});
        if(it == t[v].end()) return false;
        if((*it).first != val) return false;
        cur1 = *it;
        return 1;
    }else{
        int tm = (tl + tr) >> 1;
        return (find1(l,r,val,v+v,tl,tm) | find1(l,r,val,v+v+1,tm+1,tr));
    }
}

void upd(int pos,int val,int v = 1,int tl = 1,int tr = m - 1){
    s[v].erase({b[pos],pos});
    s[v].insert({val,pos});
    if(tl == tr) return;
    int tm = (tl + tr) >> 1;
    if(pos <= tm) upd(pos,val,v+v,tl,tm);
    else upd(pos,val,v+v+1,tm+1,tr);
}
bool find(int l,int r,int val,int v = 1,int tl = 1,int tr = m-1){
    if(tl > r || l > tr || l > r) return false;
    if(tl >= l && tr <=r){
        auto it = s[v].lower_bound({val,0});
        if(it == s[v].end()) return false;
        if((*it).first != val) return false;
        cur = *it;
        return 1;
    }else{
        int tm = (tl + tr) >> 1;
        return (find(l,r,val,v+v,tl,tm) | find(l,r,val,v+v+1,tm+1,tr));
    }
}
void test(){
    cin >> n >> m >> q;
    for(int i = 1;i <= n - 1;i++){
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    for(int i = 1;i <= m;i++){
        cin >> a[i];
        if(i > 1) b[i - 1] = lca(a[i - 1],a[i]);
    }
    if(m > 1) build();
    build1();
    while(q--){
        int tp;
        cin >> tp;
        if(tp == 1){
            int pos,v;
            cin >> pos >> v;
            if(pos < m){
                int x = lca(v,a[pos + 1]);
                upd(pos,x);
                b[pos] = x;
            }
            if(pos > 1){
                int x = lca(a[pos - 1],v);
                upd(pos - 1,x);
                b[pos - 1] = x;
            }
            upd1(pos,v);
            a[pos] = v;
        }else{
            int l,r,v;
            cin >> l >> r >> v;
            if(l == r){
                if(v == a[l]){
                    cout << l << ' ' << r << '\n';
                }else{
                    cout << -1 << ' ' << -1 << '\n';
                }
                continue;
            }
            if(find(l,r - 1,v)){
                cout << cur.second << ' ' << cur.second + 1 << '\n'; 
            }else{
                if(find1(l,r,v)){
                    cout << cur1.second << ' ' << cur1.second << '\n';
                    continue;
                }
                cout << -1 << ' ' << -1 << '\n';
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) test();
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80140 KB n=5
2 Correct 40 ms 80252 KB n=100
3 Correct 39 ms 80216 KB n=100
4 Correct 38 ms 80152 KB n=100
5 Correct 42 ms 80176 KB n=100
6 Correct 37 ms 80172 KB n=100
7 Correct 43 ms 80332 KB n=100
8 Correct 42 ms 80168 KB n=100
9 Correct 38 ms 80204 KB n=100
10 Correct 36 ms 80232 KB n=100
11 Correct 37 ms 80260 KB n=100
12 Correct 37 ms 80164 KB n=100
13 Correct 37 ms 80228 KB n=100
14 Correct 41 ms 80204 KB n=100
15 Correct 38 ms 80152 KB n=100
16 Correct 38 ms 80204 KB n=100
17 Correct 39 ms 80352 KB n=100
18 Correct 42 ms 80244 KB n=100
19 Correct 39 ms 80204 KB n=100
20 Correct 36 ms 80240 KB n=100
21 Correct 37 ms 80204 KB n=100
22 Correct 37 ms 80260 KB n=100
23 Correct 38 ms 80220 KB n=100
24 Correct 39 ms 80196 KB n=100
25 Correct 39 ms 80268 KB n=100
26 Correct 37 ms 80168 KB n=12
27 Correct 48 ms 80168 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80140 KB n=5
2 Correct 40 ms 80252 KB n=100
3 Correct 39 ms 80216 KB n=100
4 Correct 38 ms 80152 KB n=100
5 Correct 42 ms 80176 KB n=100
6 Correct 37 ms 80172 KB n=100
7 Correct 43 ms 80332 KB n=100
8 Correct 42 ms 80168 KB n=100
9 Correct 38 ms 80204 KB n=100
10 Correct 36 ms 80232 KB n=100
11 Correct 37 ms 80260 KB n=100
12 Correct 37 ms 80164 KB n=100
13 Correct 37 ms 80228 KB n=100
14 Correct 41 ms 80204 KB n=100
15 Correct 38 ms 80152 KB n=100
16 Correct 38 ms 80204 KB n=100
17 Correct 39 ms 80352 KB n=100
18 Correct 42 ms 80244 KB n=100
19 Correct 39 ms 80204 KB n=100
20 Correct 36 ms 80240 KB n=100
21 Correct 37 ms 80204 KB n=100
22 Correct 37 ms 80260 KB n=100
23 Correct 38 ms 80220 KB n=100
24 Correct 39 ms 80196 KB n=100
25 Correct 39 ms 80268 KB n=100
26 Correct 37 ms 80168 KB n=12
27 Correct 48 ms 80168 KB n=100
28 Correct 41 ms 80748 KB n=500
29 Correct 39 ms 80724 KB n=500
30 Correct 41 ms 80724 KB n=500
31 Correct 40 ms 80656 KB n=500
32 Correct 40 ms 80680 KB n=500
33 Correct 41 ms 80632 KB n=500
34 Correct 41 ms 80624 KB n=500
35 Correct 40 ms 80672 KB n=500
36 Correct 39 ms 80748 KB n=500
37 Correct 40 ms 80700 KB n=500
38 Correct 38 ms 80736 KB n=500
39 Correct 41 ms 80744 KB n=500
40 Correct 43 ms 80852 KB n=500
41 Correct 40 ms 80664 KB n=500
42 Correct 42 ms 80700 KB n=500
43 Correct 41 ms 80676 KB n=500
44 Correct 40 ms 80684 KB n=500
45 Correct 40 ms 80716 KB n=500
46 Correct 41 ms 80624 KB n=500
47 Correct 45 ms 80808 KB n=500
48 Correct 44 ms 80684 KB n=500
49 Correct 41 ms 80724 KB n=500
50 Correct 42 ms 80676 KB n=500
51 Correct 42 ms 80676 KB n=500
52 Correct 41 ms 80724 KB n=500
53 Correct 44 ms 80820 KB n=500
54 Correct 41 ms 80680 KB n=500
55 Correct 40 ms 80560 KB n=278
56 Correct 42 ms 80708 KB n=500
57 Correct 41 ms 80740 KB n=500
58 Correct 46 ms 80616 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80140 KB n=5
2 Correct 40 ms 80252 KB n=100
3 Correct 39 ms 80216 KB n=100
4 Correct 38 ms 80152 KB n=100
5 Correct 42 ms 80176 KB n=100
6 Correct 37 ms 80172 KB n=100
7 Correct 43 ms 80332 KB n=100
8 Correct 42 ms 80168 KB n=100
9 Correct 38 ms 80204 KB n=100
10 Correct 36 ms 80232 KB n=100
11 Correct 37 ms 80260 KB n=100
12 Correct 37 ms 80164 KB n=100
13 Correct 37 ms 80228 KB n=100
14 Correct 41 ms 80204 KB n=100
15 Correct 38 ms 80152 KB n=100
16 Correct 38 ms 80204 KB n=100
17 Correct 39 ms 80352 KB n=100
18 Correct 42 ms 80244 KB n=100
19 Correct 39 ms 80204 KB n=100
20 Correct 36 ms 80240 KB n=100
21 Correct 37 ms 80204 KB n=100
22 Correct 37 ms 80260 KB n=100
23 Correct 38 ms 80220 KB n=100
24 Correct 39 ms 80196 KB n=100
25 Correct 39 ms 80268 KB n=100
26 Correct 37 ms 80168 KB n=12
27 Correct 48 ms 80168 KB n=100
28 Correct 41 ms 80748 KB n=500
29 Correct 39 ms 80724 KB n=500
30 Correct 41 ms 80724 KB n=500
31 Correct 40 ms 80656 KB n=500
32 Correct 40 ms 80680 KB n=500
33 Correct 41 ms 80632 KB n=500
34 Correct 41 ms 80624 KB n=500
35 Correct 40 ms 80672 KB n=500
36 Correct 39 ms 80748 KB n=500
37 Correct 40 ms 80700 KB n=500
38 Correct 38 ms 80736 KB n=500
39 Correct 41 ms 80744 KB n=500
40 Correct 43 ms 80852 KB n=500
41 Correct 40 ms 80664 KB n=500
42 Correct 42 ms 80700 KB n=500
43 Correct 41 ms 80676 KB n=500
44 Correct 40 ms 80684 KB n=500
45 Correct 40 ms 80716 KB n=500
46 Correct 41 ms 80624 KB n=500
47 Correct 45 ms 80808 KB n=500
48 Correct 44 ms 80684 KB n=500
49 Correct 41 ms 80724 KB n=500
50 Correct 42 ms 80676 KB n=500
51 Correct 42 ms 80676 KB n=500
52 Correct 41 ms 80724 KB n=500
53 Correct 44 ms 80820 KB n=500
54 Correct 41 ms 80680 KB n=500
55 Correct 40 ms 80560 KB n=278
56 Correct 42 ms 80708 KB n=500
57 Correct 41 ms 80740 KB n=500
58 Correct 46 ms 80616 KB n=500
59 Correct 50 ms 82772 KB n=2000
60 Correct 55 ms 82780 KB n=2000
61 Correct 53 ms 82832 KB n=2000
62 Correct 52 ms 82688 KB n=2000
63 Correct 51 ms 82700 KB n=2000
64 Correct 52 ms 82724 KB n=2000
65 Correct 51 ms 82764 KB n=2000
66 Correct 54 ms 82740 KB n=2000
67 Correct 58 ms 82724 KB n=2000
68 Correct 53 ms 82764 KB n=2000
69 Correct 46 ms 82764 KB n=2000
70 Correct 43 ms 82676 KB n=2000
71 Correct 47 ms 82788 KB n=2000
72 Correct 45 ms 82788 KB n=2000
73 Correct 46 ms 82788 KB n=2000
74 Correct 50 ms 82656 KB n=1844
75 Correct 44 ms 82780 KB n=2000
76 Correct 51 ms 82732 KB n=2000
77 Correct 51 ms 82760 KB n=2000
78 Correct 51 ms 82780 KB n=2000
79 Correct 52 ms 82788 KB n=2000
80 Correct 56 ms 82852 KB n=2000
81 Correct 51 ms 82816 KB n=2000
82 Correct 51 ms 82780 KB n=2000
83 Correct 52 ms 82728 KB n=2000
84 Correct 54 ms 82796 KB n=2000
85 Correct 52 ms 82704 KB n=2000
86 Correct 55 ms 82684 KB n=2000
87 Correct 52 ms 82764 KB n=2000
88 Correct 57 ms 82868 KB n=2000
89 Correct 52 ms 82788 KB n=2000
90 Correct 55 ms 82896 KB n=2000
91 Correct 44 ms 82668 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80140 KB n=5
2 Correct 40 ms 80252 KB n=100
3 Correct 39 ms 80216 KB n=100
4 Correct 38 ms 80152 KB n=100
5 Correct 42 ms 80176 KB n=100
6 Correct 37 ms 80172 KB n=100
7 Correct 43 ms 80332 KB n=100
8 Correct 42 ms 80168 KB n=100
9 Correct 38 ms 80204 KB n=100
10 Correct 36 ms 80232 KB n=100
11 Correct 37 ms 80260 KB n=100
12 Correct 37 ms 80164 KB n=100
13 Correct 37 ms 80228 KB n=100
14 Correct 41 ms 80204 KB n=100
15 Correct 38 ms 80152 KB n=100
16 Correct 38 ms 80204 KB n=100
17 Correct 39 ms 80352 KB n=100
18 Correct 42 ms 80244 KB n=100
19 Correct 39 ms 80204 KB n=100
20 Correct 36 ms 80240 KB n=100
21 Correct 37 ms 80204 KB n=100
22 Correct 37 ms 80260 KB n=100
23 Correct 38 ms 80220 KB n=100
24 Correct 39 ms 80196 KB n=100
25 Correct 39 ms 80268 KB n=100
26 Correct 37 ms 80168 KB n=12
27 Correct 48 ms 80168 KB n=100
28 Correct 41 ms 80748 KB n=500
29 Correct 39 ms 80724 KB n=500
30 Correct 41 ms 80724 KB n=500
31 Correct 40 ms 80656 KB n=500
32 Correct 40 ms 80680 KB n=500
33 Correct 41 ms 80632 KB n=500
34 Correct 41 ms 80624 KB n=500
35 Correct 40 ms 80672 KB n=500
36 Correct 39 ms 80748 KB n=500
37 Correct 40 ms 80700 KB n=500
38 Correct 38 ms 80736 KB n=500
39 Correct 41 ms 80744 KB n=500
40 Correct 43 ms 80852 KB n=500
41 Correct 40 ms 80664 KB n=500
42 Correct 42 ms 80700 KB n=500
43 Correct 41 ms 80676 KB n=500
44 Correct 40 ms 80684 KB n=500
45 Correct 40 ms 80716 KB n=500
46 Correct 41 ms 80624 KB n=500
47 Correct 45 ms 80808 KB n=500
48 Correct 44 ms 80684 KB n=500
49 Correct 41 ms 80724 KB n=500
50 Correct 42 ms 80676 KB n=500
51 Correct 42 ms 80676 KB n=500
52 Correct 41 ms 80724 KB n=500
53 Correct 44 ms 80820 KB n=500
54 Correct 41 ms 80680 KB n=500
55 Correct 40 ms 80560 KB n=278
56 Correct 42 ms 80708 KB n=500
57 Correct 41 ms 80740 KB n=500
58 Correct 46 ms 80616 KB n=500
59 Correct 50 ms 82772 KB n=2000
60 Correct 55 ms 82780 KB n=2000
61 Correct 53 ms 82832 KB n=2000
62 Correct 52 ms 82688 KB n=2000
63 Correct 51 ms 82700 KB n=2000
64 Correct 52 ms 82724 KB n=2000
65 Correct 51 ms 82764 KB n=2000
66 Correct 54 ms 82740 KB n=2000
67 Correct 58 ms 82724 KB n=2000
68 Correct 53 ms 82764 KB n=2000
69 Correct 46 ms 82764 KB n=2000
70 Correct 43 ms 82676 KB n=2000
71 Correct 47 ms 82788 KB n=2000
72 Correct 45 ms 82788 KB n=2000
73 Correct 46 ms 82788 KB n=2000
74 Correct 50 ms 82656 KB n=1844
75 Correct 44 ms 82780 KB n=2000
76 Correct 51 ms 82732 KB n=2000
77 Correct 51 ms 82760 KB n=2000
78 Correct 51 ms 82780 KB n=2000
79 Correct 52 ms 82788 KB n=2000
80 Correct 56 ms 82852 KB n=2000
81 Correct 51 ms 82816 KB n=2000
82 Correct 51 ms 82780 KB n=2000
83 Correct 52 ms 82728 KB n=2000
84 Correct 54 ms 82796 KB n=2000
85 Correct 52 ms 82704 KB n=2000
86 Correct 55 ms 82684 KB n=2000
87 Correct 52 ms 82764 KB n=2000
88 Correct 57 ms 82868 KB n=2000
89 Correct 52 ms 82788 KB n=2000
90 Correct 55 ms 82896 KB n=2000
91 Correct 44 ms 82668 KB n=2000
92 Runtime error 359 ms 262144 KB Execution killed with signal 9
93 Halted 0 ms 0 KB -