oj.uz

Submission #909780

# Submission time Handle Problem Language Result Execution time Memory
909780 2024-01-17T12:06:58 Z daoquanglinh2007 Birthday gift (IZhO18_treearray) C++17
100 / 100
 1366 ms 113940 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 2e5, LOG = 18;
 
int n, m, q;
vector <int> adj[NM+5];
int dep[NM+5], timer = 0, tin[NM+5], tout[NM+5];
pii f[LOG+5][2*NM+5];
int a[NM+5];
set <pii> S1, S2;
set <pii>::iterator it;
 
void dfs(int u, int p){
	dep[u] = (p == -1 ? 0 : dep[p]+1);
	tin[u] = ++timer;
	f[0][timer] = mp(dep[u], u);
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
		f[0][++timer] = mp(dep[u], u);
	}
	tout[u] = timer;
}
 
void build_sparse(){
	for (int i = 1; i <= LOG; i++)
		for (int j = 1; j+(1<<i)-1 <= timer; j++)
			f[i][j] = min(f[i-1][j], f[i-1][j+(1<<(i-1))]);
}
 
int lca(int l, int r){
	l = tin[l], r = tin[r];
	if (l > r) swap(l, r);
	int k = __lg(r-l+1);
	return min(f[k][l], f[k][r-(1<<k)+1]).se;
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, -1);
	build_sparse();
	
	for (int i = 1; i <= m; i++) cin >> a[i];
	for (int i = 1; i <= m; i++){
		S1.insert(mp(a[i], i));
		if (i < m) S2.insert(mp(lca(a[i], a[i+1]), i));
	}
	
	while (q--){
		int type; cin >> type;
		if (type == 1){
			int pos, val; cin >> pos >> val;
			S1.erase(mp(a[pos], pos));
			if (pos > 1) S2.erase(mp(lca(a[pos-1], a[pos]), pos-1));
			if (pos < m) S2.erase(mp(lca(a[pos], a[pos+1]), pos));
			a[pos] = val;
			S1.insert(mp(a[pos], pos));
			if (pos > 1) S2.insert(mp(lca(a[pos-1], a[pos]), pos-1));
			if (pos < m) S2.insert(mp(lca(a[pos], a[pos+1]), pos));
		}
		else{
			int l, r, v; cin >> l >> r >> v;
			it = S1.lower_bound(mp(v, l));
			if (it != S1.end() && it->fi == v && it->se <= r){
				cout << it->se << ' ' << it->se << '\n';
				continue;
			}
			it = S2.lower_bound(mp(v, l));
			if (it != S2.end() && it->fi == v && it->se < r){
				cout << it->se << ' ' << it->se+1 << '\n';
				continue;
			}
			cout << "-1 -1\n";
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16508 KB n=5
2 Correct 6 ms 24668 KB n=100
3 Correct 5 ms 24664 KB n=100
4 Correct 5 ms 24668 KB n=100
5 Correct 6 ms 24692 KB n=100
6 Correct 6 ms 24728 KB n=100
7 Correct 6 ms 24668 KB n=100
8 Correct 6 ms 24668 KB n=100
9 Correct 5 ms 24664 KB n=100
10 Correct 7 ms 24668 KB n=100
11 Correct 7 ms 24824 KB n=100
12 Correct 6 ms 24664 KB n=100
13 Correct 6 ms 24668 KB n=100
14 Correct 5 ms 24668 KB n=100
15 Correct 6 ms 24724 KB n=100
16 Correct 6 ms 24664 KB n=100
17 Correct 5 ms 24668 KB n=100
18 Correct 6 ms 24668 KB n=100
19 Correct 5 ms 24668 KB n=100
20 Correct 6 ms 24668 KB n=100
21 Correct 6 ms 24668 KB n=100
22 Correct 6 ms 24668 KB n=100
23 Correct 6 ms 24668 KB n=100
24 Correct 6 ms 24664 KB n=100
25 Correct 6 ms 24920 KB n=100
26 Correct 4 ms 18524 KB n=12
27 Correct 6 ms 24664 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16508 KB n=5
2 Correct 6 ms 24668 KB n=100
3 Correct 5 ms 24664 KB n=100
4 Correct 5 ms 24668 KB n=100
5 Correct 6 ms 24692 KB n=100
6 Correct 6 ms 24728 KB n=100
7 Correct 6 ms 24668 KB n=100
8 Correct 6 ms 24668 KB n=100
9 Correct 5 ms 24664 KB n=100
10 Correct 7 ms 24668 KB n=100
11 Correct 7 ms 24824 KB n=100
12 Correct 6 ms 24664 KB n=100
13 Correct 6 ms 24668 KB n=100
14 Correct 5 ms 24668 KB n=100
15 Correct 6 ms 24724 KB n=100
16 Correct 6 ms 24664 KB n=100
17 Correct 5 ms 24668 KB n=100
18 Correct 6 ms 24668 KB n=100
19 Correct 5 ms 24668 KB n=100
20 Correct 6 ms 24668 KB n=100
21 Correct 6 ms 24668 KB n=100
22 Correct 6 ms 24668 KB n=100
23 Correct 6 ms 24668 KB n=100
24 Correct 6 ms 24664 KB n=100
25 Correct 6 ms 24920 KB n=100
26 Correct 4 ms 18524 KB n=12
27 Correct 6 ms 24664 KB n=100
28 Correct 7 ms 28764 KB n=500
29 Correct 6 ms 28764 KB n=500
30 Correct 7 ms 28760 KB n=500
31 Correct 7 ms 28764 KB n=500
32 Correct 6 ms 28764 KB n=500
33 Correct 7 ms 28760 KB n=500
34 Correct 7 ms 28760 KB n=500
35 Correct 8 ms 28760 KB n=500
36 Correct 7 ms 28764 KB n=500
37 Correct 7 ms 28764 KB n=500
38 Correct 6 ms 28760 KB n=500
39 Correct 7 ms 28764 KB n=500
40 Correct 7 ms 28764 KB n=500
41 Correct 6 ms 28760 KB n=500
42 Correct 7 ms 28764 KB n=500
43 Correct 7 ms 28760 KB n=500
44 Correct 6 ms 28764 KB n=500
45 Correct 6 ms 28764 KB n=500
46 Correct 7 ms 28764 KB n=500
47 Correct 7 ms 28764 KB n=500
48 Correct 7 ms 28764 KB n=500
49 Correct 7 ms 28764 KB n=500
50 Correct 7 ms 28764 KB n=500
51 Correct 7 ms 28764 KB n=500
52 Correct 7 ms 28760 KB n=500
53 Correct 6 ms 28764 KB n=500
54 Correct 6 ms 28764 KB n=500
55 Correct 7 ms 28776 KB n=278
56 Correct 8 ms 29028 KB n=500
57 Correct 8 ms 28776 KB n=500
58 Correct 8 ms 29032 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16508 KB n=5
2 Correct 6 ms 24668 KB n=100
3 Correct 5 ms 24664 KB n=100
4 Correct 5 ms 24668 KB n=100
5 Correct 6 ms 24692 KB n=100
6 Correct 6 ms 24728 KB n=100
7 Correct 6 ms 24668 KB n=100
8 Correct 6 ms 24668 KB n=100
9 Correct 5 ms 24664 KB n=100
10 Correct 7 ms 24668 KB n=100
11 Correct 7 ms 24824 KB n=100
12 Correct 6 ms 24664 KB n=100
13 Correct 6 ms 24668 KB n=100
14 Correct 5 ms 24668 KB n=100
15 Correct 6 ms 24724 KB n=100
16 Correct 6 ms 24664 KB n=100
17 Correct 5 ms 24668 KB n=100
18 Correct 6 ms 24668 KB n=100
19 Correct 5 ms 24668 KB n=100
20 Correct 6 ms 24668 KB n=100
21 Correct 6 ms 24668 KB n=100
22 Correct 6 ms 24668 KB n=100
23 Correct 6 ms 24668 KB n=100
24 Correct 6 ms 24664 KB n=100
25 Correct 6 ms 24920 KB n=100
26 Correct 4 ms 18524 KB n=12
27 Correct 6 ms 24664 KB n=100
28 Correct 7 ms 28764 KB n=500
29 Correct 6 ms 28764 KB n=500
30 Correct 7 ms 28760 KB n=500
31 Correct 7 ms 28764 KB n=500
32 Correct 6 ms 28764 KB n=500
33 Correct 7 ms 28760 KB n=500
34 Correct 7 ms 28760 KB n=500
35 Correct 8 ms 28760 KB n=500
36 Correct 7 ms 28764 KB n=500
37 Correct 7 ms 28764 KB n=500
38 Correct 6 ms 28760 KB n=500
39 Correct 7 ms 28764 KB n=500
40 Correct 7 ms 28764 KB n=500
41 Correct 6 ms 28760 KB n=500
42 Correct 7 ms 28764 KB n=500
43 Correct 7 ms 28760 KB n=500
44 Correct 6 ms 28764 KB n=500
45 Correct 6 ms 28764 KB n=500
46 Correct 7 ms 28764 KB n=500
47 Correct 7 ms 28764 KB n=500
48 Correct 7 ms 28764 KB n=500
49 Correct 7 ms 28764 KB n=500
50 Correct 7 ms 28764 KB n=500
51 Correct 7 ms 28764 KB n=500
52 Correct 7 ms 28760 KB n=500
53 Correct 6 ms 28764 KB n=500
54 Correct 6 ms 28764 KB n=500
55 Correct 7 ms 28776 KB n=278
56 Correct 8 ms 29028 KB n=500
57 Correct 8 ms 28776 KB n=500
58 Correct 8 ms 29032 KB n=500
59 Correct 9 ms 33128 KB n=2000
60 Correct 11 ms 33384 KB n=2000
61 Correct 10 ms 33116 KB n=2000
62 Correct 10 ms 33112 KB n=2000
63 Correct 10 ms 33116 KB n=2000
64 Correct 10 ms 33112 KB n=2000
65 Correct 10 ms 33368 KB n=2000
66 Correct 10 ms 33112 KB n=2000
67 Correct 10 ms 33372 KB n=2000
68 Correct 9 ms 33112 KB n=2000
69 Correct 8 ms 33112 KB n=2000
70 Correct 8 ms 33116 KB n=2000
71 Correct 9 ms 33116 KB n=2000
72 Correct 10 ms 33204 KB n=2000
73 Correct 8 ms 33116 KB n=2000
74 Correct 8 ms 33148 KB n=1844
75 Correct 9 ms 33096 KB n=2000
76 Correct 10 ms 33116 KB n=2000
77 Correct 9 ms 33116 KB n=2000
78 Correct 9 ms 33128 KB n=2000
79 Correct 10 ms 33116 KB n=2000
80 Correct 10 ms 33112 KB n=2000
81 Correct 9 ms 33112 KB n=2000
82 Correct 10 ms 33116 KB n=2000
83 Correct 10 ms 33120 KB n=2000
84 Correct 10 ms 33128 KB n=2000
85 Correct 9 ms 33116 KB n=2000
86 Correct 11 ms 33112 KB n=2000
87 Correct 10 ms 33116 KB n=2000
88 Correct 9 ms 33372 KB n=2000
89 Correct 9 ms 33372 KB n=2000
90 Correct 9 ms 33368 KB n=2000
91 Correct 9 ms 33116 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16508 KB n=5
2 Correct 6 ms 24668 KB n=100
3 Correct 5 ms 24664 KB n=100
4 Correct 5 ms 24668 KB n=100
5 Correct 6 ms 24692 KB n=100
6 Correct 6 ms 24728 KB n=100
7 Correct 6 ms 24668 KB n=100
8 Correct 6 ms 24668 KB n=100
9 Correct 5 ms 24664 KB n=100
10 Correct 7 ms 24668 KB n=100
11 Correct 7 ms 24824 KB n=100
12 Correct 6 ms 24664 KB n=100
13 Correct 6 ms 24668 KB n=100
14 Correct 5 ms 24668 KB n=100
15 Correct 6 ms 24724 KB n=100
16 Correct 6 ms 24664 KB n=100
17 Correct 5 ms 24668 KB n=100
18 Correct 6 ms 24668 KB n=100
19 Correct 5 ms 24668 KB n=100
20 Correct 6 ms 24668 KB n=100
21 Correct 6 ms 24668 KB n=100
22 Correct 6 ms 24668 KB n=100
23 Correct 6 ms 24668 KB n=100
24 Correct 6 ms 24664 KB n=100
25 Correct 6 ms 24920 KB n=100
26 Correct 4 ms 18524 KB n=12
27 Correct 6 ms 24664 KB n=100
28 Correct 7 ms 28764 KB n=500
29 Correct 6 ms 28764 KB n=500
30 Correct 7 ms 28760 KB n=500
31 Correct 7 ms 28764 KB n=500
32 Correct 6 ms 28764 KB n=500
33 Correct 7 ms 28760 KB n=500
34 Correct 7 ms 28760 KB n=500
35 Correct 8 ms 28760 KB n=500
36 Correct 7 ms 28764 KB n=500
37 Correct 7 ms 28764 KB n=500
38 Correct 6 ms 28760 KB n=500
39 Correct 7 ms 28764 KB n=500
40 Correct 7 ms 28764 KB n=500
41 Correct 6 ms 28760 KB n=500
42 Correct 7 ms 28764 KB n=500
43 Correct 7 ms 28760 KB n=500
44 Correct 6 ms 28764 KB n=500
45 Correct 6 ms 28764 KB n=500
46 Correct 7 ms 28764 KB n=500
47 Correct 7 ms 28764 KB n=500
48 Correct 7 ms 28764 KB n=500
49 Correct 7 ms 28764 KB n=500
50 Correct 7 ms 28764 KB n=500
51 Correct 7 ms 28764 KB n=500
52 Correct 7 ms 28760 KB n=500
53 Correct 6 ms 28764 KB n=500
54 Correct 6 ms 28764 KB n=500
55 Correct 7 ms 28776 KB n=278
56 Correct 8 ms 29028 KB n=500
57 Correct 8 ms 28776 KB n=500
58 Correct 8 ms 29032 KB n=500
59 Correct 9 ms 33128 KB n=2000
60 Correct 11 ms 33384 KB n=2000
61 Correct 10 ms 33116 KB n=2000
62 Correct 10 ms 33112 KB n=2000
63 Correct 10 ms 33116 KB n=2000
64 Correct 10 ms 33112 KB n=2000
65 Correct 10 ms 33368 KB n=2000
66 Correct 10 ms 33112 KB n=2000
67 Correct 10 ms 33372 KB n=2000
68 Correct 9 ms 33112 KB n=2000
69 Correct 8 ms 33112 KB n=2000
70 Correct 8 ms 33116 KB n=2000
71 Correct 9 ms 33116 KB n=2000
72 Correct 10 ms 33204 KB n=2000
73 Correct 8 ms 33116 KB n=2000
74 Correct 8 ms 33148 KB n=1844
75 Correct 9 ms 33096 KB n=2000
76 Correct 10 ms 33116 KB n=2000
77 Correct 9 ms 33116 KB n=2000
78 Correct 9 ms 33128 KB n=2000
79 Correct 10 ms 33116 KB n=2000
80 Correct 10 ms 33112 KB n=2000
81 Correct 9 ms 33112 KB n=2000
82 Correct 10 ms 33116 KB n=2000
83 Correct 10 ms 33120 KB n=2000
84 Correct 10 ms 33128 KB n=2000
85 Correct 9 ms 33116 KB n=2000
86 Correct 11 ms 33112 KB n=2000
87 Correct 10 ms 33116 KB n=2000
88 Correct 9 ms 33372 KB n=2000
89 Correct 9 ms 33372 KB n=2000
90 Correct 9 ms 33368 KB n=2000
91 Correct 9 ms 33116 KB n=2000
92 Correct 891 ms 101568 KB n=200000
93 Correct 967 ms 107856 KB n=200000
94 Correct 1016 ms 112408 KB n=200000
95 Correct 753 ms 101108 KB n=200000
96 Correct 780 ms 101380 KB n=200000
97 Correct 982 ms 106588 KB n=200000
98 Correct 825 ms 101280 KB n=200000
99 Correct 921 ms 101536 KB n=200000
100 Correct 813 ms 101208 KB n=200000
101 Correct 925 ms 113940 KB n=200000
102 Correct 399 ms 102312 KB n=200000
103 Correct 400 ms 102496 KB n=200000
104 Correct 383 ms 102484 KB n=200000
105 Correct 421 ms 102804 KB n=200000
106 Correct 461 ms 102744 KB n=200000
107 Correct 363 ms 102928 KB n=200000
108 Correct 826 ms 101204 KB n=200000
109 Correct 819 ms 101364 KB n=200000
110 Correct 899 ms 101240 KB n=200000
111 Correct 967 ms 100776 KB n=200000
112 Correct 1088 ms 112516 KB n=200000
113 Correct 1366 ms 106700 KB n=200000
114 Correct 729 ms 100728 KB n=200000
115 Correct 1043 ms 103740 KB n=200000
116 Correct 832 ms 101512 KB n=200000
117 Correct 961 ms 113364 KB n=200000
118 Correct 1033 ms 105196 KB n=200000
119 Correct 858 ms 101472 KB n=200000
120 Correct 922 ms 113000 KB n=200000
121 Correct 872 ms 113088 KB n=200000
122 Correct 914 ms 113180 KB n=200000
123 Correct 400 ms 102536 KB n=200000
124 Correct 215 ms 62300 KB n=25264