#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
const int MAXN = (int) 2e5;
const int LOG = 19;
vector <int> g[MAXN + 1];
int lvl[MAXN + 1];
int rmq[2 * MAXN + 1][LOG + 1];
int first[MAXN + 1], sz;
void dfs(int nod, int par) {
rmq[++sz][0] = nod;
first[nod] = sz;
lvl[nod] = lvl[par] + 1;
for(auto it : g[nod]) {
if(it != par) {
dfs(it, nod);
rmq[++sz][0] = nod;
}
}
}
char lg[2 * MAXN + 1];
inline void prec(int n) {
dfs(1, 0);
for(int i = 2; i <= sz; i++) {
lg[i] = lg[i >> 1] + 1;
}
for(int bit = 1; (1 << bit) <= sz; bit++) {
for(int i = 1; i + (1 << bit) <= sz + 1; i++) {
int a = rmq[i][bit - 1], b = rmq[i + (1 << (bit - 1))][bit - 1];
if(lvl[a] < lvl[b])
rmq[i][bit] = a;
else
rmq[i][bit] = b;
}
}
}
inline int get(int x, int y) {
x = first[x], y = first[y];
if(x > y) {
swap(x, y);
}
int bit = lg[y - x + 1];
int a = rmq[x][bit], b = rmq[y - (1 << bit) + 1][bit];
if(lvl[a] < lvl[b])
return a;
return b;
}
int arr[MAXN + 1];
multiset <int> mst1[MAXN + 1], mst2[MAXN + 1];
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n, m, q;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
for(i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
prec(n);
for(i = 1; i<= m; i++) {
cin >> arr[i];
}
for(i = 1; i <= m; i++) {
mst1[arr[i]].insert(i);
if(i < m) {
mst2[get(arr[i], arr[i + 1])].insert(i);
}
}
while(q > 0) {
q--;
int type;
cin >> type;
if(type == 1) {
int pos, nod;
cin >> pos >> nod;
mst1[arr[pos]].erase(mst1[arr[pos]].find(pos));
mst1[nod].insert(pos);
if(pos > 1) {
int x = get(arr[pos], arr[pos - 1]);
mst2[x].erase(mst2[x].find(pos - 1));
x = get(nod, arr[pos - 1]);
mst2[x].insert(pos - 1);
}
if(pos < m) {
int x = get(arr[pos], arr[pos + 1]);
mst2[x].erase(mst2[x].find(pos));
x = get(nod, arr[pos + 1]);
mst2[x].insert(pos);
}
arr[pos] = nod;
}
else {
int l, r, nod;
cin >> l >> r >> nod;
pair <int, int> ans = {-1, -1};
if(mst1[nod].lower_bound(l) != mst1[nod].end()) {
auto it = mst1[nod].lower_bound(l);
if(*it <= r) {
ans = {*it, *it};
}
}
if(mst2[nod].lower_bound(l) != mst2[nod].end()) {
auto it = mst2[nod].lower_bound(l);
if(*it < r) {
ans = {*it, *it + 1};
}
}
cout << ans.first << " " << ans.second << "\n";
}
}
//cin.close();
//cout.close();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
23800 KB |
n=5 |
2 |
Correct |
20 ms |
23816 KB |
n=100 |
3 |
Correct |
19 ms |
23804 KB |
n=100 |
4 |
Correct |
22 ms |
23928 KB |
n=100 |
5 |
Correct |
20 ms |
23928 KB |
n=100 |
6 |
Correct |
19 ms |
23800 KB |
n=100 |
7 |
Correct |
19 ms |
23800 KB |
n=100 |
8 |
Correct |
20 ms |
23800 KB |
n=100 |
9 |
Correct |
19 ms |
23800 KB |
n=100 |
10 |
Correct |
19 ms |
23800 KB |
n=100 |
11 |
Correct |
20 ms |
23900 KB |
n=100 |
12 |
Correct |
23 ms |
23848 KB |
n=100 |
13 |
Correct |
21 ms |
23928 KB |
n=100 |
14 |
Correct |
19 ms |
23800 KB |
n=100 |
15 |
Correct |
19 ms |
23928 KB |
n=100 |
16 |
Correct |
19 ms |
23800 KB |
n=100 |
17 |
Correct |
19 ms |
23928 KB |
n=100 |
18 |
Correct |
19 ms |
23800 KB |
n=100 |
19 |
Correct |
19 ms |
23900 KB |
n=100 |
20 |
Correct |
23 ms |
23928 KB |
n=100 |
21 |
Correct |
23 ms |
23928 KB |
n=100 |
22 |
Correct |
23 ms |
23800 KB |
n=100 |
23 |
Correct |
23 ms |
23928 KB |
n=100 |
24 |
Correct |
23 ms |
23800 KB |
n=100 |
25 |
Correct |
23 ms |
23928 KB |
n=100 |
26 |
Correct |
23 ms |
23900 KB |
n=12 |
27 |
Correct |
23 ms |
23900 KB |
n=100 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
23800 KB |
n=5 |
2 |
Correct |
20 ms |
23816 KB |
n=100 |
3 |
Correct |
19 ms |
23804 KB |
n=100 |
4 |
Correct |
22 ms |
23928 KB |
n=100 |
5 |
Correct |
20 ms |
23928 KB |
n=100 |
6 |
Correct |
19 ms |
23800 KB |
n=100 |
7 |
Correct |
19 ms |
23800 KB |
n=100 |
8 |
Correct |
20 ms |
23800 KB |
n=100 |
9 |
Correct |
19 ms |
23800 KB |
n=100 |
10 |
Correct |
19 ms |
23800 KB |
n=100 |
11 |
Correct |
20 ms |
23900 KB |
n=100 |
12 |
Correct |
23 ms |
23848 KB |
n=100 |
13 |
Correct |
21 ms |
23928 KB |
n=100 |
14 |
Correct |
19 ms |
23800 KB |
n=100 |
15 |
Correct |
19 ms |
23928 KB |
n=100 |
16 |
Correct |
19 ms |
23800 KB |
n=100 |
17 |
Correct |
19 ms |
23928 KB |
n=100 |
18 |
Correct |
19 ms |
23800 KB |
n=100 |
19 |
Correct |
19 ms |
23900 KB |
n=100 |
20 |
Correct |
23 ms |
23928 KB |
n=100 |
21 |
Correct |
23 ms |
23928 KB |
n=100 |
22 |
Correct |
23 ms |
23800 KB |
n=100 |
23 |
Correct |
23 ms |
23928 KB |
n=100 |
24 |
Correct |
23 ms |
23800 KB |
n=100 |
25 |
Correct |
23 ms |
23928 KB |
n=100 |
26 |
Correct |
23 ms |
23900 KB |
n=12 |
27 |
Correct |
23 ms |
23900 KB |
n=100 |
28 |
Correct |
20 ms |
23928 KB |
n=500 |
29 |
Correct |
20 ms |
24056 KB |
n=500 |
30 |
Correct |
24 ms |
24056 KB |
n=500 |
31 |
Correct |
23 ms |
23980 KB |
n=500 |
32 |
Correct |
24 ms |
24052 KB |
n=500 |
33 |
Correct |
23 ms |
24056 KB |
n=500 |
34 |
Correct |
22 ms |
24056 KB |
n=500 |
35 |
Correct |
23 ms |
24056 KB |
n=500 |
36 |
Correct |
24 ms |
23984 KB |
n=500 |
37 |
Correct |
23 ms |
23932 KB |
n=500 |
38 |
Correct |
23 ms |
23932 KB |
n=500 |
39 |
Correct |
23 ms |
23928 KB |
n=500 |
40 |
Correct |
23 ms |
24056 KB |
n=500 |
41 |
Correct |
23 ms |
24056 KB |
n=500 |
42 |
Correct |
23 ms |
24056 KB |
n=500 |
43 |
Correct |
23 ms |
23928 KB |
n=500 |
44 |
Correct |
23 ms |
23928 KB |
n=500 |
45 |
Correct |
23 ms |
23944 KB |
n=500 |
46 |
Correct |
23 ms |
23928 KB |
n=500 |
47 |
Correct |
23 ms |
24004 KB |
n=500 |
48 |
Correct |
20 ms |
23928 KB |
n=500 |
49 |
Correct |
20 ms |
23928 KB |
n=500 |
50 |
Correct |
20 ms |
23956 KB |
n=500 |
51 |
Correct |
24 ms |
24056 KB |
n=500 |
52 |
Correct |
23 ms |
24056 KB |
n=500 |
53 |
Correct |
20 ms |
23928 KB |
n=500 |
54 |
Correct |
19 ms |
23928 KB |
n=500 |
55 |
Correct |
19 ms |
23928 KB |
n=278 |
56 |
Correct |
19 ms |
23928 KB |
n=500 |
57 |
Correct |
19 ms |
23928 KB |
n=500 |
58 |
Correct |
19 ms |
23928 KB |
n=500 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
23800 KB |
n=5 |
2 |
Correct |
20 ms |
23816 KB |
n=100 |
3 |
Correct |
19 ms |
23804 KB |
n=100 |
4 |
Correct |
22 ms |
23928 KB |
n=100 |
5 |
Correct |
20 ms |
23928 KB |
n=100 |
6 |
Correct |
19 ms |
23800 KB |
n=100 |
7 |
Correct |
19 ms |
23800 KB |
n=100 |
8 |
Correct |
20 ms |
23800 KB |
n=100 |
9 |
Correct |
19 ms |
23800 KB |
n=100 |
10 |
Correct |
19 ms |
23800 KB |
n=100 |
11 |
Correct |
20 ms |
23900 KB |
n=100 |
12 |
Correct |
23 ms |
23848 KB |
n=100 |
13 |
Correct |
21 ms |
23928 KB |
n=100 |
14 |
Correct |
19 ms |
23800 KB |
n=100 |
15 |
Correct |
19 ms |
23928 KB |
n=100 |
16 |
Correct |
19 ms |
23800 KB |
n=100 |
17 |
Correct |
19 ms |
23928 KB |
n=100 |
18 |
Correct |
19 ms |
23800 KB |
n=100 |
19 |
Correct |
19 ms |
23900 KB |
n=100 |
20 |
Correct |
23 ms |
23928 KB |
n=100 |
21 |
Correct |
23 ms |
23928 KB |
n=100 |
22 |
Correct |
23 ms |
23800 KB |
n=100 |
23 |
Correct |
23 ms |
23928 KB |
n=100 |
24 |
Correct |
23 ms |
23800 KB |
n=100 |
25 |
Correct |
23 ms |
23928 KB |
n=100 |
26 |
Correct |
23 ms |
23900 KB |
n=12 |
27 |
Correct |
23 ms |
23900 KB |
n=100 |
28 |
Correct |
20 ms |
23928 KB |
n=500 |
29 |
Correct |
20 ms |
24056 KB |
n=500 |
30 |
Correct |
24 ms |
24056 KB |
n=500 |
31 |
Correct |
23 ms |
23980 KB |
n=500 |
32 |
Correct |
24 ms |
24052 KB |
n=500 |
33 |
Correct |
23 ms |
24056 KB |
n=500 |
34 |
Correct |
22 ms |
24056 KB |
n=500 |
35 |
Correct |
23 ms |
24056 KB |
n=500 |
36 |
Correct |
24 ms |
23984 KB |
n=500 |
37 |
Correct |
23 ms |
23932 KB |
n=500 |
38 |
Correct |
23 ms |
23932 KB |
n=500 |
39 |
Correct |
23 ms |
23928 KB |
n=500 |
40 |
Correct |
23 ms |
24056 KB |
n=500 |
41 |
Correct |
23 ms |
24056 KB |
n=500 |
42 |
Correct |
23 ms |
24056 KB |
n=500 |
43 |
Correct |
23 ms |
23928 KB |
n=500 |
44 |
Correct |
23 ms |
23928 KB |
n=500 |
45 |
Correct |
23 ms |
23944 KB |
n=500 |
46 |
Correct |
23 ms |
23928 KB |
n=500 |
47 |
Correct |
23 ms |
24004 KB |
n=500 |
48 |
Correct |
20 ms |
23928 KB |
n=500 |
49 |
Correct |
20 ms |
23928 KB |
n=500 |
50 |
Correct |
20 ms |
23956 KB |
n=500 |
51 |
Correct |
24 ms |
24056 KB |
n=500 |
52 |
Correct |
23 ms |
24056 KB |
n=500 |
53 |
Correct |
20 ms |
23928 KB |
n=500 |
54 |
Correct |
19 ms |
23928 KB |
n=500 |
55 |
Correct |
19 ms |
23928 KB |
n=278 |
56 |
Correct |
19 ms |
23928 KB |
n=500 |
57 |
Correct |
19 ms |
23928 KB |
n=500 |
58 |
Correct |
19 ms |
23928 KB |
n=500 |
59 |
Correct |
22 ms |
24440 KB |
n=2000 |
60 |
Correct |
21 ms |
24568 KB |
n=2000 |
61 |
Correct |
22 ms |
24440 KB |
n=2000 |
62 |
Correct |
23 ms |
24440 KB |
n=2000 |
63 |
Correct |
23 ms |
24572 KB |
n=2000 |
64 |
Correct |
23 ms |
24440 KB |
n=2000 |
65 |
Correct |
22 ms |
24412 KB |
n=2000 |
66 |
Correct |
21 ms |
24440 KB |
n=2000 |
67 |
Correct |
23 ms |
24440 KB |
n=2000 |
68 |
Correct |
22 ms |
24440 KB |
n=2000 |
69 |
Correct |
23 ms |
24440 KB |
n=2000 |
70 |
Correct |
22 ms |
24440 KB |
n=2000 |
71 |
Correct |
22 ms |
24504 KB |
n=2000 |
72 |
Correct |
21 ms |
24440 KB |
n=2000 |
73 |
Correct |
46 ms |
24440 KB |
n=2000 |
74 |
Correct |
22 ms |
24384 KB |
n=1844 |
75 |
Correct |
21 ms |
24440 KB |
n=2000 |
76 |
Correct |
37 ms |
24568 KB |
n=2000 |
77 |
Correct |
22 ms |
24440 KB |
n=2000 |
78 |
Correct |
23 ms |
24440 KB |
n=2000 |
79 |
Correct |
23 ms |
24440 KB |
n=2000 |
80 |
Correct |
23 ms |
24584 KB |
n=2000 |
81 |
Correct |
22 ms |
24440 KB |
n=2000 |
82 |
Correct |
55 ms |
24440 KB |
n=2000 |
83 |
Correct |
23 ms |
24568 KB |
n=2000 |
84 |
Correct |
22 ms |
24440 KB |
n=2000 |
85 |
Correct |
23 ms |
24552 KB |
n=2000 |
86 |
Correct |
23 ms |
24440 KB |
n=2000 |
87 |
Correct |
23 ms |
24440 KB |
n=2000 |
88 |
Correct |
22 ms |
24568 KB |
n=2000 |
89 |
Correct |
22 ms |
24568 KB |
n=2000 |
90 |
Correct |
21 ms |
24568 KB |
n=2000 |
91 |
Correct |
22 ms |
24440 KB |
n=2000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
23800 KB |
n=5 |
2 |
Correct |
20 ms |
23816 KB |
n=100 |
3 |
Correct |
19 ms |
23804 KB |
n=100 |
4 |
Correct |
22 ms |
23928 KB |
n=100 |
5 |
Correct |
20 ms |
23928 KB |
n=100 |
6 |
Correct |
19 ms |
23800 KB |
n=100 |
7 |
Correct |
19 ms |
23800 KB |
n=100 |
8 |
Correct |
20 ms |
23800 KB |
n=100 |
9 |
Correct |
19 ms |
23800 KB |
n=100 |
10 |
Correct |
19 ms |
23800 KB |
n=100 |
11 |
Correct |
20 ms |
23900 KB |
n=100 |
12 |
Correct |
23 ms |
23848 KB |
n=100 |
13 |
Correct |
21 ms |
23928 KB |
n=100 |
14 |
Correct |
19 ms |
23800 KB |
n=100 |
15 |
Correct |
19 ms |
23928 KB |
n=100 |
16 |
Correct |
19 ms |
23800 KB |
n=100 |
17 |
Correct |
19 ms |
23928 KB |
n=100 |
18 |
Correct |
19 ms |
23800 KB |
n=100 |
19 |
Correct |
19 ms |
23900 KB |
n=100 |
20 |
Correct |
23 ms |
23928 KB |
n=100 |
21 |
Correct |
23 ms |
23928 KB |
n=100 |
22 |
Correct |
23 ms |
23800 KB |
n=100 |
23 |
Correct |
23 ms |
23928 KB |
n=100 |
24 |
Correct |
23 ms |
23800 KB |
n=100 |
25 |
Correct |
23 ms |
23928 KB |
n=100 |
26 |
Correct |
23 ms |
23900 KB |
n=12 |
27 |
Correct |
23 ms |
23900 KB |
n=100 |
28 |
Correct |
20 ms |
23928 KB |
n=500 |
29 |
Correct |
20 ms |
24056 KB |
n=500 |
30 |
Correct |
24 ms |
24056 KB |
n=500 |
31 |
Correct |
23 ms |
23980 KB |
n=500 |
32 |
Correct |
24 ms |
24052 KB |
n=500 |
33 |
Correct |
23 ms |
24056 KB |
n=500 |
34 |
Correct |
22 ms |
24056 KB |
n=500 |
35 |
Correct |
23 ms |
24056 KB |
n=500 |
36 |
Correct |
24 ms |
23984 KB |
n=500 |
37 |
Correct |
23 ms |
23932 KB |
n=500 |
38 |
Correct |
23 ms |
23932 KB |
n=500 |
39 |
Correct |
23 ms |
23928 KB |
n=500 |
40 |
Correct |
23 ms |
24056 KB |
n=500 |
41 |
Correct |
23 ms |
24056 KB |
n=500 |
42 |
Correct |
23 ms |
24056 KB |
n=500 |
43 |
Correct |
23 ms |
23928 KB |
n=500 |
44 |
Correct |
23 ms |
23928 KB |
n=500 |
45 |
Correct |
23 ms |
23944 KB |
n=500 |
46 |
Correct |
23 ms |
23928 KB |
n=500 |
47 |
Correct |
23 ms |
24004 KB |
n=500 |
48 |
Correct |
20 ms |
23928 KB |
n=500 |
49 |
Correct |
20 ms |
23928 KB |
n=500 |
50 |
Correct |
20 ms |
23956 KB |
n=500 |
51 |
Correct |
24 ms |
24056 KB |
n=500 |
52 |
Correct |
23 ms |
24056 KB |
n=500 |
53 |
Correct |
20 ms |
23928 KB |
n=500 |
54 |
Correct |
19 ms |
23928 KB |
n=500 |
55 |
Correct |
19 ms |
23928 KB |
n=278 |
56 |
Correct |
19 ms |
23928 KB |
n=500 |
57 |
Correct |
19 ms |
23928 KB |
n=500 |
58 |
Correct |
19 ms |
23928 KB |
n=500 |
59 |
Correct |
22 ms |
24440 KB |
n=2000 |
60 |
Correct |
21 ms |
24568 KB |
n=2000 |
61 |
Correct |
22 ms |
24440 KB |
n=2000 |
62 |
Correct |
23 ms |
24440 KB |
n=2000 |
63 |
Correct |
23 ms |
24572 KB |
n=2000 |
64 |
Correct |
23 ms |
24440 KB |
n=2000 |
65 |
Correct |
22 ms |
24412 KB |
n=2000 |
66 |
Correct |
21 ms |
24440 KB |
n=2000 |
67 |
Correct |
23 ms |
24440 KB |
n=2000 |
68 |
Correct |
22 ms |
24440 KB |
n=2000 |
69 |
Correct |
23 ms |
24440 KB |
n=2000 |
70 |
Correct |
22 ms |
24440 KB |
n=2000 |
71 |
Correct |
22 ms |
24504 KB |
n=2000 |
72 |
Correct |
21 ms |
24440 KB |
n=2000 |
73 |
Correct |
46 ms |
24440 KB |
n=2000 |
74 |
Correct |
22 ms |
24384 KB |
n=1844 |
75 |
Correct |
21 ms |
24440 KB |
n=2000 |
76 |
Correct |
37 ms |
24568 KB |
n=2000 |
77 |
Correct |
22 ms |
24440 KB |
n=2000 |
78 |
Correct |
23 ms |
24440 KB |
n=2000 |
79 |
Correct |
23 ms |
24440 KB |
n=2000 |
80 |
Correct |
23 ms |
24584 KB |
n=2000 |
81 |
Correct |
22 ms |
24440 KB |
n=2000 |
82 |
Correct |
55 ms |
24440 KB |
n=2000 |
83 |
Correct |
23 ms |
24568 KB |
n=2000 |
84 |
Correct |
22 ms |
24440 KB |
n=2000 |
85 |
Correct |
23 ms |
24552 KB |
n=2000 |
86 |
Correct |
23 ms |
24440 KB |
n=2000 |
87 |
Correct |
23 ms |
24440 KB |
n=2000 |
88 |
Correct |
22 ms |
24568 KB |
n=2000 |
89 |
Correct |
22 ms |
24568 KB |
n=2000 |
90 |
Correct |
21 ms |
24568 KB |
n=2000 |
91 |
Correct |
22 ms |
24440 KB |
n=2000 |
92 |
Correct |
1084 ms |
91420 KB |
n=200000 |
93 |
Correct |
1123 ms |
96348 KB |
n=200000 |
94 |
Correct |
871 ms |
99792 KB |
n=200000 |
95 |
Correct |
1002 ms |
91444 KB |
n=200000 |
96 |
Correct |
764 ms |
91164 KB |
n=200000 |
97 |
Correct |
799 ms |
95612 KB |
n=200000 |
98 |
Correct |
1154 ms |
91368 KB |
n=200000 |
99 |
Correct |
1271 ms |
91400 KB |
n=200000 |
100 |
Correct |
836 ms |
91248 KB |
n=200000 |
101 |
Correct |
889 ms |
101072 KB |
n=200000 |
102 |
Correct |
454 ms |
92464 KB |
n=200000 |
103 |
Correct |
524 ms |
92632 KB |
n=200000 |
104 |
Correct |
600 ms |
92408 KB |
n=200000 |
105 |
Correct |
471 ms |
92856 KB |
n=200000 |
106 |
Correct |
630 ms |
93048 KB |
n=200000 |
107 |
Correct |
618 ms |
92792 KB |
n=200000 |
108 |
Correct |
1133 ms |
91484 KB |
n=200000 |
109 |
Correct |
1118 ms |
91344 KB |
n=200000 |
110 |
Correct |
931 ms |
91448 KB |
n=200000 |
111 |
Correct |
810 ms |
90736 KB |
n=200000 |
112 |
Correct |
796 ms |
100048 KB |
n=200000 |
113 |
Correct |
925 ms |
95408 KB |
n=200000 |
114 |
Correct |
954 ms |
90956 KB |
n=200000 |
115 |
Correct |
1222 ms |
93412 KB |
n=200000 |
116 |
Correct |
1089 ms |
91380 KB |
n=200000 |
117 |
Correct |
939 ms |
100392 KB |
n=200000 |
118 |
Correct |
1166 ms |
94392 KB |
n=200000 |
119 |
Correct |
927 ms |
91460 KB |
n=200000 |
120 |
Correct |
724 ms |
99980 KB |
n=200000 |
121 |
Correct |
687 ms |
100008 KB |
n=200000 |
122 |
Correct |
883 ms |
100356 KB |
n=200000 |
123 |
Correct |
494 ms |
92716 KB |
n=200000 |
124 |
Correct |
181 ms |
40824 KB |
n=25264 |