oj.uz

Submission #683294

# Submission time Handle Problem Language Result Execution time Memory
683294 2023-01-18T06:26:48 Z Dima_Borchuk Birthday gift (IZhO18_treearray) C++17
100 / 100
 977 ms 115364 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) int32_t(x.size())
#define pii pair<int,int>
#include<bits/stdc++.h>
#define ld long double
#define ll long long
#define _ << ' ' <<
//#define int ll

using namespace std;
using namespace __gnu_pbds;

const int p = 1009;
const int L = 20;
const int N = (int)3e5 + 5;
const int INF = (int)2e18 + 6;
const int mod = (int)998244353;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

template <typename T>
using ordered_set = tree < T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update >;

int a[N], up[N][20], tin[N], tout[N];

vector < int > g[N];

int timer = 0;

void dfs(int v, int anc) {
    tin[v] = ++timer;
    up[v][0] = anc;
    for (int i = 1; i < 20; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }

    for (auto to : g[v]) {
        if (to == anc) continue;
        dfs(to, v);
    }

    tout[v] = ++timer;
}

bool upper(int a, int b) {
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 19; i >= 0; i--) {
        if (up[a][i] && !upper(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

set < int > s[N], t[N];

int32_t main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m, q;
    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];
        s[a[i]].insert(i);
    }
    dfs(1, 0);
    for (int i = 2; i <= m; i++) {
        t[lca(a[i], a[i - 1])].insert(i);
    }
    for (int i = 1; i <= n; i++) {
        s[i].insert(m + 1); t[i].insert(m + 1);
    }

    while (q--) {
        int type;
        cin >> type;
        if (type == 2) {
            int l, r, v;
            cin >> l >> r >> v;
            int d = *s[v].lower_bound(l), e = *t[v].lower_bound(l + 1);
            if (d <= r) {
                cout << d << ' ' << d << '\n';
            }
            else {
                if (e <= r) {
                    cout << e - 1 << ' ' << e << '\n';
                }
                else {
                    cout << "-1 -1\n";
                }
            }
        }
        else {
            int pos, v;
            cin >> pos >> v;

            s[a[pos]].erase(pos);
            s[v].insert(pos);
            if (pos > 1) t[lca(a[pos], a[pos - 1])].erase(pos);
            if (pos <= m) t[lca(a[pos + 1], a[pos])].erase(pos + 1);
            a[pos] = v;
            if (pos > 1) t[lca(a[pos], a[pos - 1])].insert(pos);
            if (pos <= m) t[lca(a[pos + 1], a[pos])].insert(pos + 1);
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35456 KB n=5
2 Correct 21 ms 35540 KB n=100
3 Correct 21 ms 35508 KB n=100
4 Correct 19 ms 35560 KB n=100
5 Correct 18 ms 35560 KB n=100
6 Correct 18 ms 35540 KB n=100
7 Correct 18 ms 35600 KB n=100
8 Correct 18 ms 35560 KB n=100
9 Correct 24 ms 35540 KB n=100
10 Correct 19 ms 35560 KB n=100
11 Correct 18 ms 35560 KB n=100
12 Correct 17 ms 35540 KB n=100
13 Correct 18 ms 35556 KB n=100
14 Correct 18 ms 35616 KB n=100
15 Correct 20 ms 35564 KB n=100
16 Correct 19 ms 35540 KB n=100
17 Correct 20 ms 35608 KB n=100
18 Correct 19 ms 35540 KB n=100
19 Correct 17 ms 35540 KB n=100
20 Correct 20 ms 35512 KB n=100
21 Correct 20 ms 35508 KB n=100
22 Correct 17 ms 35560 KB n=100
23 Correct 19 ms 35540 KB n=100
24 Correct 19 ms 35560 KB n=100
25 Correct 18 ms 35612 KB n=100
26 Correct 17 ms 35468 KB n=12
27 Correct 17 ms 35540 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35456 KB n=5
2 Correct 21 ms 35540 KB n=100
3 Correct 21 ms 35508 KB n=100
4 Correct 19 ms 35560 KB n=100
5 Correct 18 ms 35560 KB n=100
6 Correct 18 ms 35540 KB n=100
7 Correct 18 ms 35600 KB n=100
8 Correct 18 ms 35560 KB n=100
9 Correct 24 ms 35540 KB n=100
10 Correct 19 ms 35560 KB n=100
11 Correct 18 ms 35560 KB n=100
12 Correct 17 ms 35540 KB n=100
13 Correct 18 ms 35556 KB n=100
14 Correct 18 ms 35616 KB n=100
15 Correct 20 ms 35564 KB n=100
16 Correct 19 ms 35540 KB n=100
17 Correct 20 ms 35608 KB n=100
18 Correct 19 ms 35540 KB n=100
19 Correct 17 ms 35540 KB n=100
20 Correct 20 ms 35512 KB n=100
21 Correct 20 ms 35508 KB n=100
22 Correct 17 ms 35560 KB n=100
23 Correct 19 ms 35540 KB n=100
24 Correct 19 ms 35560 KB n=100
25 Correct 18 ms 35612 KB n=100
26 Correct 17 ms 35468 KB n=12
27 Correct 17 ms 35540 KB n=100
28 Correct 18 ms 35668 KB n=500
29 Correct 17 ms 35708 KB n=500
30 Correct 21 ms 35708 KB n=500
31 Correct 23 ms 35688 KB n=500
32 Correct 18 ms 35668 KB n=500
33 Correct 18 ms 35668 KB n=500
34 Correct 18 ms 35668 KB n=500
35 Correct 18 ms 35668 KB n=500
36 Correct 18 ms 35740 KB n=500
37 Correct 19 ms 35664 KB n=500
38 Correct 22 ms 35692 KB n=500
39 Correct 20 ms 35756 KB n=500
40 Correct 19 ms 35756 KB n=500
41 Correct 18 ms 35696 KB n=500
42 Correct 19 ms 35660 KB n=500
43 Correct 18 ms 35696 KB n=500
44 Correct 18 ms 35672 KB n=500
45 Correct 19 ms 35720 KB n=500
46 Correct 18 ms 35744 KB n=500
47 Correct 17 ms 35760 KB n=500
48 Correct 18 ms 35708 KB n=500
49 Correct 22 ms 35700 KB n=500
50 Correct 18 ms 35668 KB n=500
51 Correct 18 ms 35748 KB n=500
52 Correct 18 ms 35656 KB n=500
53 Correct 19 ms 35684 KB n=500
54 Correct 19 ms 35684 KB n=500
55 Correct 17 ms 35592 KB n=278
56 Correct 19 ms 35692 KB n=500
57 Correct 18 ms 35692 KB n=500
58 Correct 18 ms 35688 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35456 KB n=5
2 Correct 21 ms 35540 KB n=100
3 Correct 21 ms 35508 KB n=100
4 Correct 19 ms 35560 KB n=100
5 Correct 18 ms 35560 KB n=100
6 Correct 18 ms 35540 KB n=100
7 Correct 18 ms 35600 KB n=100
8 Correct 18 ms 35560 KB n=100
9 Correct 24 ms 35540 KB n=100
10 Correct 19 ms 35560 KB n=100
11 Correct 18 ms 35560 KB n=100
12 Correct 17 ms 35540 KB n=100
13 Correct 18 ms 35556 KB n=100
14 Correct 18 ms 35616 KB n=100
15 Correct 20 ms 35564 KB n=100
16 Correct 19 ms 35540 KB n=100
17 Correct 20 ms 35608 KB n=100
18 Correct 19 ms 35540 KB n=100
19 Correct 17 ms 35540 KB n=100
20 Correct 20 ms 35512 KB n=100
21 Correct 20 ms 35508 KB n=100
22 Correct 17 ms 35560 KB n=100
23 Correct 19 ms 35540 KB n=100
24 Correct 19 ms 35560 KB n=100
25 Correct 18 ms 35612 KB n=100
26 Correct 17 ms 35468 KB n=12
27 Correct 17 ms 35540 KB n=100
28 Correct 18 ms 35668 KB n=500
29 Correct 17 ms 35708 KB n=500
30 Correct 21 ms 35708 KB n=500
31 Correct 23 ms 35688 KB n=500
32 Correct 18 ms 35668 KB n=500
33 Correct 18 ms 35668 KB n=500
34 Correct 18 ms 35668 KB n=500
35 Correct 18 ms 35668 KB n=500
36 Correct 18 ms 35740 KB n=500
37 Correct 19 ms 35664 KB n=500
38 Correct 22 ms 35692 KB n=500
39 Correct 20 ms 35756 KB n=500
40 Correct 19 ms 35756 KB n=500
41 Correct 18 ms 35696 KB n=500
42 Correct 19 ms 35660 KB n=500
43 Correct 18 ms 35696 KB n=500
44 Correct 18 ms 35672 KB n=500
45 Correct 19 ms 35720 KB n=500
46 Correct 18 ms 35744 KB n=500
47 Correct 17 ms 35760 KB n=500
48 Correct 18 ms 35708 KB n=500
49 Correct 22 ms 35700 KB n=500
50 Correct 18 ms 35668 KB n=500
51 Correct 18 ms 35748 KB n=500
52 Correct 18 ms 35656 KB n=500
53 Correct 19 ms 35684 KB n=500
54 Correct 19 ms 35684 KB n=500
55 Correct 17 ms 35592 KB n=278
56 Correct 19 ms 35692 KB n=500
57 Correct 18 ms 35692 KB n=500
58 Correct 18 ms 35688 KB n=500
59 Correct 21 ms 36180 KB n=2000
60 Correct 28 ms 36256 KB n=2000
61 Correct 22 ms 36268 KB n=2000
62 Correct 21 ms 36236 KB n=2000
63 Correct 21 ms 36140 KB n=2000
64 Correct 22 ms 36260 KB n=2000
65 Correct 28 ms 36136 KB n=2000
66 Correct 21 ms 36172 KB n=2000
67 Correct 23 ms 36152 KB n=2000
68 Correct 22 ms 36212 KB n=2000
69 Correct 21 ms 36152 KB n=2000
70 Correct 21 ms 36172 KB n=2000
71 Correct 21 ms 36224 KB n=2000
72 Correct 21 ms 36184 KB n=2000
73 Correct 25 ms 36172 KB n=2000
74 Correct 20 ms 36108 KB n=1844
75 Correct 20 ms 36176 KB n=2000
76 Correct 21 ms 36212 KB n=2000
77 Correct 21 ms 36144 KB n=2000
78 Correct 21 ms 36180 KB n=2000
79 Correct 21 ms 36248 KB n=2000
80 Correct 23 ms 36212 KB n=2000
81 Correct 25 ms 36192 KB n=2000
82 Correct 24 ms 36212 KB n=2000
83 Correct 23 ms 36292 KB n=2000
84 Correct 21 ms 36260 KB n=2000
85 Correct 23 ms 36264 KB n=2000
86 Correct 21 ms 36180 KB n=2000
87 Correct 22 ms 36132 KB n=2000
88 Correct 23 ms 36300 KB n=2000
89 Correct 21 ms 36220 KB n=2000
90 Correct 19 ms 36308 KB n=2000
91 Correct 19 ms 36176 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35456 KB n=5
2 Correct 21 ms 35540 KB n=100
3 Correct 21 ms 35508 KB n=100
4 Correct 19 ms 35560 KB n=100
5 Correct 18 ms 35560 KB n=100
6 Correct 18 ms 35540 KB n=100
7 Correct 18 ms 35600 KB n=100
8 Correct 18 ms 35560 KB n=100
9 Correct 24 ms 35540 KB n=100
10 Correct 19 ms 35560 KB n=100
11 Correct 18 ms 35560 KB n=100
12 Correct 17 ms 35540 KB n=100
13 Correct 18 ms 35556 KB n=100
14 Correct 18 ms 35616 KB n=100
15 Correct 20 ms 35564 KB n=100
16 Correct 19 ms 35540 KB n=100
17 Correct 20 ms 35608 KB n=100
18 Correct 19 ms 35540 KB n=100
19 Correct 17 ms 35540 KB n=100
20 Correct 20 ms 35512 KB n=100
21 Correct 20 ms 35508 KB n=100
22 Correct 17 ms 35560 KB n=100
23 Correct 19 ms 35540 KB n=100
24 Correct 19 ms 35560 KB n=100
25 Correct 18 ms 35612 KB n=100
26 Correct 17 ms 35468 KB n=12
27 Correct 17 ms 35540 KB n=100
28 Correct 18 ms 35668 KB n=500
29 Correct 17 ms 35708 KB n=500
30 Correct 21 ms 35708 KB n=500
31 Correct 23 ms 35688 KB n=500
32 Correct 18 ms 35668 KB n=500
33 Correct 18 ms 35668 KB n=500
34 Correct 18 ms 35668 KB n=500
35 Correct 18 ms 35668 KB n=500
36 Correct 18 ms 35740 KB n=500
37 Correct 19 ms 35664 KB n=500
38 Correct 22 ms 35692 KB n=500
39 Correct 20 ms 35756 KB n=500
40 Correct 19 ms 35756 KB n=500
41 Correct 18 ms 35696 KB n=500
42 Correct 19 ms 35660 KB n=500
43 Correct 18 ms 35696 KB n=500
44 Correct 18 ms 35672 KB n=500
45 Correct 19 ms 35720 KB n=500
46 Correct 18 ms 35744 KB n=500
47 Correct 17 ms 35760 KB n=500
48 Correct 18 ms 35708 KB n=500
49 Correct 22 ms 35700 KB n=500
50 Correct 18 ms 35668 KB n=500
51 Correct 18 ms 35748 KB n=500
52 Correct 18 ms 35656 KB n=500
53 Correct 19 ms 35684 KB n=500
54 Correct 19 ms 35684 KB n=500
55 Correct 17 ms 35592 KB n=278
56 Correct 19 ms 35692 KB n=500
57 Correct 18 ms 35692 KB n=500
58 Correct 18 ms 35688 KB n=500
59 Correct 21 ms 36180 KB n=2000
60 Correct 28 ms 36256 KB n=2000
61 Correct 22 ms 36268 KB n=2000
62 Correct 21 ms 36236 KB n=2000
63 Correct 21 ms 36140 KB n=2000
64 Correct 22 ms 36260 KB n=2000
65 Correct 28 ms 36136 KB n=2000
66 Correct 21 ms 36172 KB n=2000
67 Correct 23 ms 36152 KB n=2000
68 Correct 22 ms 36212 KB n=2000
69 Correct 21 ms 36152 KB n=2000
70 Correct 21 ms 36172 KB n=2000
71 Correct 21 ms 36224 KB n=2000
72 Correct 21 ms 36184 KB n=2000
73 Correct 25 ms 36172 KB n=2000
74 Correct 20 ms 36108 KB n=1844
75 Correct 20 ms 36176 KB n=2000
76 Correct 21 ms 36212 KB n=2000
77 Correct 21 ms 36144 KB n=2000
78 Correct 21 ms 36180 KB n=2000
79 Correct 21 ms 36248 KB n=2000
80 Correct 23 ms 36212 KB n=2000
81 Correct 25 ms 36192 KB n=2000
82 Correct 24 ms 36212 KB n=2000
83 Correct 23 ms 36292 KB n=2000
84 Correct 21 ms 36260 KB n=2000
85 Correct 23 ms 36264 KB n=2000
86 Correct 21 ms 36180 KB n=2000
87 Correct 22 ms 36132 KB n=2000
88 Correct 23 ms 36300 KB n=2000
89 Correct 21 ms 36220 KB n=2000
90 Correct 19 ms 36308 KB n=2000
91 Correct 19 ms 36176 KB n=2000
92 Correct 670 ms 104680 KB n=200000
93 Correct 798 ms 110664 KB n=200000
94 Correct 668 ms 114000 KB n=200000
95 Correct 696 ms 105604 KB n=200000
96 Correct 663 ms 105776 KB n=200000
97 Correct 903 ms 109924 KB n=200000
98 Correct 685 ms 105748 KB n=200000
99 Correct 762 ms 105904 KB n=200000
100 Correct 674 ms 105792 KB n=200000
101 Correct 590 ms 115364 KB n=200000
102 Correct 441 ms 107024 KB n=200000
103 Correct 436 ms 106956 KB n=200000
104 Correct 421 ms 106844 KB n=200000
105 Correct 414 ms 107196 KB n=200000
106 Correct 442 ms 107324 KB n=200000
107 Correct 420 ms 107256 KB n=200000
108 Correct 713 ms 105852 KB n=200000
109 Correct 691 ms 105828 KB n=200000
110 Correct 681 ms 105740 KB n=200000
111 Correct 688 ms 105192 KB n=200000
112 Correct 702 ms 114380 KB n=200000
113 Correct 837 ms 109936 KB n=200000
114 Correct 704 ms 105192 KB n=200000
115 Correct 977 ms 107852 KB n=200000
116 Correct 631 ms 105824 KB n=200000
117 Correct 595 ms 114728 KB n=200000
118 Correct 926 ms 108600 KB n=200000
119 Correct 619 ms 105924 KB n=200000
120 Correct 549 ms 114356 KB n=200000
121 Correct 528 ms 114272 KB n=200000
122 Correct 532 ms 114584 KB n=200000
123 Correct 422 ms 107108 KB n=200000
124 Correct 154 ms 52908 KB n=25264