oj.uz

Submission #1011035

# Submission time Handle Problem Language Result Execution time Memory
1011035 2024-06-29T17:20:56 Z phoenix Birthday gift (IZhO18_treearray) C++17
100 / 100
 560 ms 83280 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

vector<int> g[N];
int tin[N], tout[N], T;
int par[N][18];

void precalc(int s, int p) {
    tin[s] = T++;
    par[s][0] = p;
    for (int i = 1; i < 18; i++) par[s][i] = par[par[s][i - 1]][i - 1];
    for (int to : g[s]) if (to != p)
        precalc(to, s);
    tout[s] = T++;
}

bool up(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (up(u, v)) return u;
    if (up(v, u)) return v;
    for (int i = 17; i >= 0; i--) 
        if (!up(par[u][i], v))
            u = par[u][i];
    return par[u][0];
}

int n, m, q;
int A[N];

set<int> s1[N], s2[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= m; i++)
        cin >> A[i];
    A[0] = A[m + 1] = 1;
    precalc(1, 1);
    for (int i = 0; i <= m; i++) {
        s1[lca(A[i], A[i + 1])].insert(i);
        s2[A[i]].insert(i);
    }
    
    while (q --> 0) {
        int t;
        cin >> t;
        if (t == 1) {
            int pos, v;
            cin >> pos >> v;
            s2[A[pos]].erase(pos);
            s1[lca(A[pos], A[pos + 1])].erase(pos);
            s1[lca(A[pos - 1], A[pos])].erase(pos - 1);
            A[pos] = v;
            s2[A[pos]].insert(pos);
            s1[lca(A[pos], A[pos + 1])].insert(pos);
            s1[lca(A[pos - 1], A[pos])].insert(pos - 1);
        } else {
            int l, r, v;
            cin >> l >> r >> v;
            auto it = s1[v].lower_bound(l);
            if (it != s1[v].end() && *it < r) 
                cout << *it << ' ' << *it + 1;
            else {
                it = s2[v].lower_bound(l);
                if (it != s2[v].end() && *it <= r) 
                    cout << *it << ' ' << *it;
                else 
                    cout << -1 << ' ' << -1;
            }
            cout << '\n';
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 11 ms 23900 KB n=100
3 Correct 10 ms 23896 KB n=100
4 Correct 10 ms 23896 KB n=100
5 Correct 10 ms 23900 KB n=100
6 Correct 10 ms 24148 KB n=100
7 Correct 10 ms 23900 KB n=100
8 Correct 10 ms 23900 KB n=100
9 Correct 10 ms 23900 KB n=100
10 Correct 10 ms 23796 KB n=100
11 Correct 11 ms 23900 KB n=100
12 Correct 10 ms 23896 KB n=100
13 Correct 10 ms 23896 KB n=100
14 Correct 10 ms 23896 KB n=100
15 Correct 13 ms 23896 KB n=100
16 Correct 10 ms 23900 KB n=100
17 Correct 11 ms 23900 KB n=100
18 Correct 11 ms 23900 KB n=100
19 Correct 11 ms 23900 KB n=100
20 Correct 10 ms 23896 KB n=100
21 Correct 10 ms 23900 KB n=100
22 Correct 10 ms 23900 KB n=100
23 Correct 11 ms 23900 KB n=100
24 Correct 10 ms 23896 KB n=100
25 Correct 10 ms 23896 KB n=100
26 Correct 10 ms 23900 KB n=12
27 Correct 11 ms 23900 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 11 ms 23900 KB n=100
3 Correct 10 ms 23896 KB n=100
4 Correct 10 ms 23896 KB n=100
5 Correct 10 ms 23900 KB n=100
6 Correct 10 ms 24148 KB n=100
7 Correct 10 ms 23900 KB n=100
8 Correct 10 ms 23900 KB n=100
9 Correct 10 ms 23900 KB n=100
10 Correct 10 ms 23796 KB n=100
11 Correct 11 ms 23900 KB n=100
12 Correct 10 ms 23896 KB n=100
13 Correct 10 ms 23896 KB n=100
14 Correct 10 ms 23896 KB n=100
15 Correct 13 ms 23896 KB n=100
16 Correct 10 ms 23900 KB n=100
17 Correct 11 ms 23900 KB n=100
18 Correct 11 ms 23900 KB n=100
19 Correct 11 ms 23900 KB n=100
20 Correct 10 ms 23896 KB n=100
21 Correct 10 ms 23900 KB n=100
22 Correct 10 ms 23900 KB n=100
23 Correct 11 ms 23900 KB n=100
24 Correct 10 ms 23896 KB n=100
25 Correct 10 ms 23896 KB n=100
26 Correct 10 ms 23900 KB n=12
27 Correct 11 ms 23900 KB n=100
28 Correct 10 ms 24152 KB n=500
29 Correct 13 ms 23900 KB n=500
30 Correct 10 ms 23900 KB n=500
31 Correct 11 ms 23900 KB n=500
32 Correct 10 ms 23900 KB n=500
33 Correct 11 ms 23932 KB n=500
34 Correct 11 ms 23900 KB n=500
35 Correct 13 ms 23896 KB n=500
36 Correct 11 ms 23900 KB n=500
37 Correct 10 ms 23900 KB n=500
38 Correct 10 ms 23900 KB n=500
39 Correct 12 ms 23900 KB n=500
40 Correct 10 ms 23900 KB n=500
41 Correct 11 ms 23896 KB n=500
42 Correct 12 ms 23864 KB n=500
43 Correct 11 ms 23896 KB n=500
44 Correct 11 ms 23900 KB n=500
45 Correct 12 ms 24112 KB n=500
46 Correct 10 ms 23980 KB n=500
47 Correct 10 ms 23900 KB n=500
48 Correct 11 ms 23896 KB n=500
49 Correct 10 ms 23900 KB n=500
50 Correct 11 ms 23900 KB n=500
51 Correct 11 ms 23900 KB n=500
52 Correct 11 ms 23900 KB n=500
53 Correct 11 ms 23896 KB n=500
54 Correct 10 ms 23900 KB n=500
55 Correct 11 ms 23896 KB n=278
56 Correct 10 ms 23900 KB n=500
57 Correct 10 ms 23900 KB n=500
58 Correct 10 ms 23896 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 11 ms 23900 KB n=100
3 Correct 10 ms 23896 KB n=100
4 Correct 10 ms 23896 KB n=100
5 Correct 10 ms 23900 KB n=100
6 Correct 10 ms 24148 KB n=100
7 Correct 10 ms 23900 KB n=100
8 Correct 10 ms 23900 KB n=100
9 Correct 10 ms 23900 KB n=100
10 Correct 10 ms 23796 KB n=100
11 Correct 11 ms 23900 KB n=100
12 Correct 10 ms 23896 KB n=100
13 Correct 10 ms 23896 KB n=100
14 Correct 10 ms 23896 KB n=100
15 Correct 13 ms 23896 KB n=100
16 Correct 10 ms 23900 KB n=100
17 Correct 11 ms 23900 KB n=100
18 Correct 11 ms 23900 KB n=100
19 Correct 11 ms 23900 KB n=100
20 Correct 10 ms 23896 KB n=100
21 Correct 10 ms 23900 KB n=100
22 Correct 10 ms 23900 KB n=100
23 Correct 11 ms 23900 KB n=100
24 Correct 10 ms 23896 KB n=100
25 Correct 10 ms 23896 KB n=100
26 Correct 10 ms 23900 KB n=12
27 Correct 11 ms 23900 KB n=100
28 Correct 10 ms 24152 KB n=500
29 Correct 13 ms 23900 KB n=500
30 Correct 10 ms 23900 KB n=500
31 Correct 11 ms 23900 KB n=500
32 Correct 10 ms 23900 KB n=500
33 Correct 11 ms 23932 KB n=500
34 Correct 11 ms 23900 KB n=500
35 Correct 13 ms 23896 KB n=500
36 Correct 11 ms 23900 KB n=500
37 Correct 10 ms 23900 KB n=500
38 Correct 10 ms 23900 KB n=500
39 Correct 12 ms 23900 KB n=500
40 Correct 10 ms 23900 KB n=500
41 Correct 11 ms 23896 KB n=500
42 Correct 12 ms 23864 KB n=500
43 Correct 11 ms 23896 KB n=500
44 Correct 11 ms 23900 KB n=500
45 Correct 12 ms 24112 KB n=500
46 Correct 10 ms 23980 KB n=500
47 Correct 10 ms 23900 KB n=500
48 Correct 11 ms 23896 KB n=500
49 Correct 10 ms 23900 KB n=500
50 Correct 11 ms 23900 KB n=500
51 Correct 11 ms 23900 KB n=500
52 Correct 11 ms 23900 KB n=500
53 Correct 11 ms 23896 KB n=500
54 Correct 10 ms 23900 KB n=500
55 Correct 11 ms 23896 KB n=278
56 Correct 10 ms 23900 KB n=500
57 Correct 10 ms 23900 KB n=500
58 Correct 10 ms 23896 KB n=500
59 Correct 15 ms 24412 KB n=2000
60 Correct 13 ms 24412 KB n=2000
61 Correct 12 ms 24412 KB n=2000
62 Correct 13 ms 24412 KB n=2000
63 Correct 13 ms 24408 KB n=2000
64 Correct 12 ms 24412 KB n=2000
65 Correct 12 ms 24412 KB n=2000
66 Correct 12 ms 24412 KB n=2000
67 Correct 13 ms 24412 KB n=2000
68 Correct 12 ms 24408 KB n=2000
69 Correct 12 ms 24412 KB n=2000
70 Correct 12 ms 24408 KB n=2000
71 Correct 12 ms 24408 KB n=2000
72 Correct 11 ms 24412 KB n=2000
73 Correct 12 ms 24412 KB n=2000
74 Correct 13 ms 24412 KB n=1844
75 Correct 15 ms 24464 KB n=2000
76 Correct 13 ms 24408 KB n=2000
77 Correct 16 ms 24412 KB n=2000
78 Correct 13 ms 24412 KB n=2000
79 Correct 12 ms 24460 KB n=2000
80 Correct 13 ms 24336 KB n=2000
81 Correct 12 ms 24412 KB n=2000
82 Correct 13 ms 24412 KB n=2000
83 Correct 12 ms 24412 KB n=2000
84 Correct 13 ms 24248 KB n=2000
85 Correct 13 ms 24408 KB n=2000
86 Correct 12 ms 24412 KB n=2000
87 Correct 13 ms 24364 KB n=2000
88 Correct 12 ms 24412 KB n=2000
89 Correct 11 ms 24492 KB n=2000
90 Correct 12 ms 24412 KB n=2000
91 Correct 12 ms 24412 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 11 ms 23900 KB n=100
3 Correct 10 ms 23896 KB n=100
4 Correct 10 ms 23896 KB n=100
5 Correct 10 ms 23900 KB n=100
6 Correct 10 ms 24148 KB n=100
7 Correct 10 ms 23900 KB n=100
8 Correct 10 ms 23900 KB n=100
9 Correct 10 ms 23900 KB n=100
10 Correct 10 ms 23796 KB n=100
11 Correct 11 ms 23900 KB n=100
12 Correct 10 ms 23896 KB n=100
13 Correct 10 ms 23896 KB n=100
14 Correct 10 ms 23896 KB n=100
15 Correct 13 ms 23896 KB n=100
16 Correct 10 ms 23900 KB n=100
17 Correct 11 ms 23900 KB n=100
18 Correct 11 ms 23900 KB n=100
19 Correct 11 ms 23900 KB n=100
20 Correct 10 ms 23896 KB n=100
21 Correct 10 ms 23900 KB n=100
22 Correct 10 ms 23900 KB n=100
23 Correct 11 ms 23900 KB n=100
24 Correct 10 ms 23896 KB n=100
25 Correct 10 ms 23896 KB n=100
26 Correct 10 ms 23900 KB n=12
27 Correct 11 ms 23900 KB n=100
28 Correct 10 ms 24152 KB n=500
29 Correct 13 ms 23900 KB n=500
30 Correct 10 ms 23900 KB n=500
31 Correct 11 ms 23900 KB n=500
32 Correct 10 ms 23900 KB n=500
33 Correct 11 ms 23932 KB n=500
34 Correct 11 ms 23900 KB n=500
35 Correct 13 ms 23896 KB n=500
36 Correct 11 ms 23900 KB n=500
37 Correct 10 ms 23900 KB n=500
38 Correct 10 ms 23900 KB n=500
39 Correct 12 ms 23900 KB n=500
40 Correct 10 ms 23900 KB n=500
41 Correct 11 ms 23896 KB n=500
42 Correct 12 ms 23864 KB n=500
43 Correct 11 ms 23896 KB n=500
44 Correct 11 ms 23900 KB n=500
45 Correct 12 ms 24112 KB n=500
46 Correct 10 ms 23980 KB n=500
47 Correct 10 ms 23900 KB n=500
48 Correct 11 ms 23896 KB n=500
49 Correct 10 ms 23900 KB n=500
50 Correct 11 ms 23900 KB n=500
51 Correct 11 ms 23900 KB n=500
52 Correct 11 ms 23900 KB n=500
53 Correct 11 ms 23896 KB n=500
54 Correct 10 ms 23900 KB n=500
55 Correct 11 ms 23896 KB n=278
56 Correct 10 ms 23900 KB n=500
57 Correct 10 ms 23900 KB n=500
58 Correct 10 ms 23896 KB n=500
59 Correct 15 ms 24412 KB n=2000
60 Correct 13 ms 24412 KB n=2000
61 Correct 12 ms 24412 KB n=2000
62 Correct 13 ms 24412 KB n=2000
63 Correct 13 ms 24408 KB n=2000
64 Correct 12 ms 24412 KB n=2000
65 Correct 12 ms 24412 KB n=2000
66 Correct 12 ms 24412 KB n=2000
67 Correct 13 ms 24412 KB n=2000
68 Correct 12 ms 24408 KB n=2000
69 Correct 12 ms 24412 KB n=2000
70 Correct 12 ms 24408 KB n=2000
71 Correct 12 ms 24408 KB n=2000
72 Correct 11 ms 24412 KB n=2000
73 Correct 12 ms 24412 KB n=2000
74 Correct 13 ms 24412 KB n=1844
75 Correct 15 ms 24464 KB n=2000
76 Correct 13 ms 24408 KB n=2000
77 Correct 16 ms 24412 KB n=2000
78 Correct 13 ms 24412 KB n=2000
79 Correct 12 ms 24460 KB n=2000
80 Correct 13 ms 24336 KB n=2000
81 Correct 12 ms 24412 KB n=2000
82 Correct 13 ms 24412 KB n=2000
83 Correct 12 ms 24412 KB n=2000
84 Correct 13 ms 24248 KB n=2000
85 Correct 13 ms 24408 KB n=2000
86 Correct 12 ms 24412 KB n=2000
87 Correct 13 ms 24364 KB n=2000
88 Correct 12 ms 24412 KB n=2000
89 Correct 11 ms 24492 KB n=2000
90 Correct 12 ms 24412 KB n=2000
91 Correct 12 ms 24412 KB n=2000
92 Correct 476 ms 73812 KB n=200000
93 Correct 519 ms 78880 KB n=200000
94 Correct 337 ms 82004 KB n=200000
95 Correct 438 ms 73668 KB n=200000
96 Correct 449 ms 73528 KB n=200000
97 Correct 517 ms 77760 KB n=200000
98 Correct 449 ms 73516 KB n=200000
99 Correct 510 ms 73812 KB n=200000
100 Correct 429 ms 73744 KB n=200000
101 Correct 276 ms 83280 KB n=200000
102 Correct 260 ms 74772 KB n=200000
103 Correct 254 ms 74932 KB n=200000
104 Correct 254 ms 74836 KB n=200000
105 Correct 262 ms 75240 KB n=200000
106 Correct 277 ms 75348 KB n=200000
107 Correct 249 ms 75344 KB n=200000
108 Correct 485 ms 73812 KB n=200000
109 Correct 409 ms 73812 KB n=200000
110 Correct 441 ms 73596 KB n=200000
111 Correct 431 ms 73032 KB n=200000
112 Correct 331 ms 82248 KB n=200000
113 Correct 469 ms 77692 KB n=200000
114 Correct 417 ms 73224 KB n=200000
115 Correct 560 ms 75600 KB n=200000
116 Correct 391 ms 73672 KB n=200000
117 Correct 316 ms 82772 KB n=200000
118 Correct 537 ms 76664 KB n=200000
119 Correct 398 ms 74144 KB n=200000
120 Correct 267 ms 82260 KB n=200000
121 Correct 260 ms 82256 KB n=200000
122 Correct 242 ms 82512 KB n=200000
123 Correct 273 ms 75092 KB n=200000
124 Correct 87 ms 38740 KB n=25264