oj.uz

Submission #376031

# Submission time Handle Problem Language Result Execution time Memory
376031 2021-03-10T17:43:30 Z ijxjdjd Birthday gift (IZhO18_treearray) C++14
100 / 100
 1186 ms 75784 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = (int)(2e5) + 5;
const int MAXK = 20;
int a[MAXN];
vector<int> adj[MAXN];
int timer = 0;
int tin[MAXN];
int tout[MAXN];
int up[MAXN][MAXK];
set<pair<int, int>> sts[MAXN];
void root(int n, int p) {
    up[n][0] = p;
    tin[n] = timer++;
    for (int i = 1; i < MAXK; i++) {
        up[n][i] = up[up[n][i-1]][i-1];
    }
    for (int e : adj[n]) {
        if (e != p) {
            root(e, n);
        }
    }
    tout[n] = timer++;
}
bool is_ancestor(int u, int v) {
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int lca(int x, int y) {
    if (is_ancestor(x, y)) {
        return x;
    }
    if (is_ancestor(y, x)) {
        return y;
    }
    for (int i = MAXK-1; i >= 0; i--) {
        if (!is_ancestor(up[x][i], y)) {
            x = up[x][i];
        }
    }
    return up[x][0];
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	FR(i, N-1) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
	}
	root(1, 1);
	for (int i = 1; i <= M; i++) cin >> a[i];
	for (int pos = 1; pos <= M; pos++) {
        if (pos > 1) {
            int lc = lca(a[pos], a[pos-1]);
            sts[lc].insert({pos-1, pos});
        }
        sts[a[pos]].insert({pos, -1});
	}
    FR(iter, Q) {
        int id;
        cin >> id;
        if (id == 1) {
            int pos, v;
            cin >> pos >> v;
            if (pos > 1) {
                int lc = lca(a[pos], a[pos-1]);
                sts[lc].erase({pos-1, pos});
                lc = lca(a[pos-1], v);
                sts[lc].insert({pos-1, pos});
            }
            if (pos < M) {
                int lc = lca(a[pos], a[pos+1]);
                sts[lc].erase({pos, pos+1});
                lc = lca(a[pos+1], v);
                sts[lc].insert({pos, pos+1});
            }
            sts[a[pos]].erase({pos, -1});
            sts[v].insert({pos, -1});
            a[pos] = v;
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            auto it = (sts[v].lower_bound({l, -1}));
            if (it != sts[v].end() && ((*it) <= make_pair(r, -1))) {
                if ((*it).second == -1) {
                    cout << (*it).first << " " << (*it).first << '\n';
                }
                else {
                    cout << (*it).first << " " << (*it).second << '\n';
                }
            }
            else {
                cout << "-1 -1" << '\n';

            }
        }
    }
	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB n=5
2 Correct 10 ms 14444 KB n=100
3 Correct 10 ms 14444 KB n=100
4 Correct 10 ms 14444 KB n=100
5 Correct 10 ms 14444 KB n=100
6 Correct 10 ms 14444 KB n=100
7 Correct 10 ms 14444 KB n=100
8 Correct 10 ms 14444 KB n=100
9 Correct 10 ms 14444 KB n=100
10 Correct 10 ms 14444 KB n=100
11 Correct 10 ms 14444 KB n=100
12 Correct 10 ms 14444 KB n=100
13 Correct 10 ms 14444 KB n=100
14 Correct 10 ms 14444 KB n=100
15 Correct 10 ms 14444 KB n=100
16 Correct 10 ms 14444 KB n=100
17 Correct 10 ms 14464 KB n=100
18 Correct 12 ms 14444 KB n=100
19 Correct 10 ms 14444 KB n=100
20 Correct 10 ms 14464 KB n=100
21 Correct 11 ms 14444 KB n=100
22 Correct 10 ms 14444 KB n=100
23 Correct 10 ms 14444 KB n=100
24 Correct 12 ms 14444 KB n=100
25 Correct 10 ms 14444 KB n=100
26 Correct 10 ms 14464 KB n=12
27 Correct 10 ms 14444 KB n=100
28 Correct 11 ms 14572 KB n=500
29 Correct 11 ms 14572 KB n=500
30 Correct 11 ms 14572 KB n=500
31 Correct 11 ms 14572 KB n=500
32 Correct 11 ms 14572 KB n=500
33 Correct 11 ms 14572 KB n=500
34 Correct 11 ms 14572 KB n=500
35 Correct 11 ms 14572 KB n=500
36 Correct 11 ms 14572 KB n=500
37 Correct 11 ms 14572 KB n=500
38 Correct 11 ms 14572 KB n=500
39 Correct 11 ms 14592 KB n=500
40 Correct 11 ms 14572 KB n=500
41 Correct 11 ms 14572 KB n=500
42 Correct 11 ms 14572 KB n=500
43 Correct 13 ms 14572 KB n=500
44 Correct 11 ms 14572 KB n=500
45 Correct 11 ms 14572 KB n=500
46 Correct 11 ms 14572 KB n=500
47 Correct 12 ms 14572 KB n=500
48 Correct 12 ms 14572 KB n=500
49 Correct 11 ms 14572 KB n=500
50 Correct 11 ms 14592 KB n=500
51 Correct 11 ms 14592 KB n=500
52 Correct 11 ms 14572 KB n=500
53 Correct 11 ms 14700 KB n=500
54 Correct 11 ms 14572 KB n=500
55 Correct 11 ms 14572 KB n=278
56 Correct 11 ms 14572 KB n=500
57 Correct 11 ms 14572 KB n=500
58 Correct 11 ms 14572 KB n=500
59 Correct 14 ms 14956 KB n=2000
60 Correct 13 ms 15084 KB n=2000
61 Correct 14 ms 14956 KB n=2000
62 Correct 15 ms 15084 KB n=2000
63 Correct 14 ms 14956 KB n=2000
64 Correct 14 ms 15084 KB n=2000
65 Correct 15 ms 14956 KB n=2000
66 Correct 16 ms 15084 KB n=2000
67 Correct 18 ms 14956 KB n=2000
68 Correct 14 ms 14956 KB n=2000
69 Correct 14 ms 14956 KB n=2000
70 Correct 13 ms 14956 KB n=2000
71 Correct 15 ms 14956 KB n=2000
72 Correct 13 ms 14956 KB n=2000
73 Correct 13 ms 14956 KB n=2000
74 Correct 14 ms 14956 KB n=1844
75 Correct 13 ms 14956 KB n=2000
76 Correct 14 ms 14956 KB n=2000
77 Correct 14 ms 14956 KB n=2000
78 Correct 14 ms 14956 KB n=2000
79 Correct 14 ms 14956 KB n=2000
80 Correct 13 ms 15084 KB n=2000
81 Correct 14 ms 14956 KB n=2000
82 Correct 17 ms 14996 KB n=2000
83 Correct 16 ms 14956 KB n=2000
84 Correct 15 ms 14976 KB n=2000
85 Correct 14 ms 14956 KB n=2000
86 Correct 14 ms 14956 KB n=2000
87 Correct 14 ms 14956 KB n=2000
88 Correct 13 ms 15212 KB n=2000
89 Correct 14 ms 15084 KB n=2000
90 Correct 13 ms 15084 KB n=2000
91 Correct 13 ms 14956 KB n=2000
92 Correct 964 ms 66096 KB n=200000
93 Correct 894 ms 71020 KB n=200000
94 Correct 648 ms 74348 KB n=200000
95 Correct 900 ms 66044 KB n=200000
96 Correct 919 ms 65760 KB n=200000
97 Correct 992 ms 70104 KB n=200000
98 Correct 920 ms 65964 KB n=200000
99 Correct 1074 ms 66084 KB n=200000
100 Correct 923 ms 65784 KB n=200000
101 Correct 579 ms 75784 KB n=200000
102 Correct 515 ms 67052 KB n=200000
103 Correct 511 ms 67180 KB n=200000
104 Correct 525 ms 67180 KB n=200000
105 Correct 527 ms 67436 KB n=200000
106 Correct 524 ms 67436 KB n=200000
107 Correct 516 ms 67436 KB n=200000
108 Correct 967 ms 66028 KB n=200000
109 Correct 966 ms 66028 KB n=200000
110 Correct 957 ms 66144 KB n=200000
111 Correct 913 ms 65252 KB n=200000
112 Correct 620 ms 74604 KB n=200000
113 Correct 960 ms 70252 KB n=200000
114 Correct 905 ms 65612 KB n=200000
115 Correct 1186 ms 67956 KB n=200000
116 Correct 809 ms 66016 KB n=200000
117 Correct 590 ms 75116 KB n=200000
118 Correct 1070 ms 68964 KB n=200000
119 Correct 833 ms 66056 KB n=200000
120 Correct 525 ms 74476 KB n=200000
121 Correct 516 ms 74476 KB n=200000
122 Correct 520 ms 74988 KB n=200000
123 Correct 555 ms 67252 KB n=200000
124 Correct 184 ms 29420 KB n=25264