oj.uz

Submission #505011

# Submission time Handle Problem Language Result Execution time Memory
505011 2022-01-10T11:41:41 Z Mazaalai Birthday gift (IZhO18_treearray) C++17
100 / 100
 929 ms 81096 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
const int M = 20;
int n, m, q;
int nums[N], vals[N], lvl[N];
int jump[N][M];
set <int> positions[N], positions1[N];
vector <int> paths[N];
int jumpUp(int pos, int len) {
	for (int i = 0; (1<<i)<=len; i++) 
		if (len & (1<<i)) 
			pos = jump[pos][i];
	
	return pos;
}
int LCA(int a, int b) {
	if (lvl[a] > lvl[b]) swap(a, b);
	int dif = lvl[b] - lvl[a];
	b = jumpUp(b, dif);
	for (int i = M-1; i >= 0 && a != b; i--) {
		if (jump[a][i] != jump[b][i]) {
			a = jump[a][i];
			b = jump[b][i];
		}
	}
	if (a != b) a = jump[a][0];
	return a;
}
void dfs(int pos, int par, int curLvl) {
	lvl[pos] = curLvl;
	jump[pos][0] = par;
	for (auto& el : paths[pos]) {
		if (el == par) continue;
		dfs(el, pos, curLvl+1);
	}
}
void init() {
	dfs(1, 1, 0);
	for (int i = 1; i <= n; i++) 
	for (int j = 1; j < M; j++) {
		int x = jump[i][j-1];
		jump[i][j] = jump[x][j-1];
	}
}
void update(int pos) {
	if (pos > 1) { // left
		int x = LCA(nums[pos], nums[pos-1]);
		int y = vals[pos-1];
		vals[pos-1] = x;
		if (y > 0) positions[y].erase(pos-1);
		positions[x].insert(pos-1);
	}
	if (pos + 1 <= m) { // right
		int x = LCA(nums[pos], nums[pos+1]);
		int y = vals[pos];
		vals[pos] = x;
		if (y > 0) positions[y].erase(pos);
		positions[x].insert(pos);
	}
}
signed main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		paths[a].pb(b);
		paths[b].pb(a);
	}
	for (int i = 1; i <= m; i++) cin >> nums[i];
	init();
	memset(vals, -1, sizeof(vals));
	for (int i = 1; i <= m; i++) {
		positions1[nums[i]].insert(i);
		update(i);
	}
	// for (int i = 1; i < m; i++) cout << vals[i] << " \n"[i==m-1];
	for (int i = 0; i < q; i++) {
		int a, b, c;
		cin >> a;
		if (a == 2) {
			cin >> a >> b >> c; // query from l to r, find V
			set <int>& cur = positions[c];
			set <int>& cur1 = positions1[c];
			auto it = cur.lower_bound(a);
			auto it1 = cur1.lower_bound(a);
			int x = -1, y = -1;
			if (it != cur.end() && *it < b) {
				x = *it; 
				y = x+1;
			}
			if (x == -1 && it1 != cur1.end() && *it1 <= b) {
				x = y = *it1;
			}
			cout << x << ' ' << y << '\n';
		} else {
			// cout << "UPDATE\n";
			cin >> a >> b; // update 
			positions1[nums[a]].erase(a);
			nums[a] = b;
			positions1[nums[a]].insert(a);
			update(a);
		}
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24524 KB n=5
2 Correct 11 ms 24524 KB n=100
3 Correct 11 ms 24524 KB n=100
4 Correct 11 ms 24524 KB n=100
5 Correct 11 ms 24572 KB n=100
6 Correct 11 ms 24612 KB n=100
7 Correct 11 ms 24516 KB n=100
8 Correct 11 ms 24524 KB n=100
9 Correct 11 ms 24524 KB n=100
10 Correct 11 ms 24524 KB n=100
11 Correct 13 ms 24576 KB n=100
12 Correct 11 ms 24524 KB n=100
13 Correct 11 ms 24560 KB n=100
14 Correct 11 ms 24524 KB n=100
15 Correct 11 ms 24616 KB n=100
16 Correct 12 ms 24652 KB n=100
17 Correct 12 ms 24524 KB n=100
18 Correct 11 ms 24552 KB n=100
19 Correct 13 ms 24564 KB n=100
20 Correct 11 ms 24524 KB n=100
21 Correct 11 ms 24588 KB n=100
22 Correct 12 ms 24576 KB n=100
23 Correct 10 ms 24524 KB n=100
24 Correct 11 ms 24524 KB n=100
25 Correct 11 ms 24524 KB n=100
26 Correct 10 ms 24568 KB n=12
27 Correct 11 ms 24572 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24524 KB n=5
2 Correct 11 ms 24524 KB n=100
3 Correct 11 ms 24524 KB n=100
4 Correct 11 ms 24524 KB n=100
5 Correct 11 ms 24572 KB n=100
6 Correct 11 ms 24612 KB n=100
7 Correct 11 ms 24516 KB n=100
8 Correct 11 ms 24524 KB n=100
9 Correct 11 ms 24524 KB n=100
10 Correct 11 ms 24524 KB n=100
11 Correct 13 ms 24576 KB n=100
12 Correct 11 ms 24524 KB n=100
13 Correct 11 ms 24560 KB n=100
14 Correct 11 ms 24524 KB n=100
15 Correct 11 ms 24616 KB n=100
16 Correct 12 ms 24652 KB n=100
17 Correct 12 ms 24524 KB n=100
18 Correct 11 ms 24552 KB n=100
19 Correct 13 ms 24564 KB n=100
20 Correct 11 ms 24524 KB n=100
21 Correct 11 ms 24588 KB n=100
22 Correct 12 ms 24576 KB n=100
23 Correct 10 ms 24524 KB n=100
24 Correct 11 ms 24524 KB n=100
25 Correct 11 ms 24524 KB n=100
26 Correct 10 ms 24568 KB n=12
27 Correct 11 ms 24572 KB n=100
28 Correct 12 ms 24668 KB n=500
29 Correct 11 ms 24772 KB n=500
30 Correct 12 ms 24728 KB n=500
31 Correct 12 ms 24692 KB n=500
32 Correct 12 ms 24780 KB n=500
33 Correct 12 ms 24716 KB n=500
34 Correct 12 ms 24652 KB n=500
35 Correct 12 ms 24652 KB n=500
36 Correct 12 ms 24652 KB n=500
37 Correct 12 ms 24692 KB n=500
38 Correct 14 ms 24700 KB n=500
39 Correct 14 ms 24652 KB n=500
40 Correct 11 ms 24652 KB n=500
41 Correct 11 ms 24636 KB n=500
42 Correct 12 ms 24708 KB n=500
43 Correct 12 ms 24612 KB n=500
44 Correct 12 ms 24708 KB n=500
45 Correct 12 ms 24712 KB n=500
46 Correct 12 ms 24732 KB n=500
47 Correct 12 ms 24652 KB n=500
48 Correct 12 ms 24652 KB n=500
49 Correct 11 ms 24712 KB n=500
50 Correct 15 ms 24644 KB n=500
51 Correct 13 ms 24632 KB n=500
52 Correct 12 ms 24708 KB n=500
53 Correct 12 ms 24716 KB n=500
54 Correct 11 ms 24652 KB n=500
55 Correct 11 ms 24652 KB n=278
56 Correct 13 ms 24652 KB n=500
57 Correct 14 ms 24700 KB n=500
58 Correct 11 ms 24652 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24524 KB n=5
2 Correct 11 ms 24524 KB n=100
3 Correct 11 ms 24524 KB n=100
4 Correct 11 ms 24524 KB n=100
5 Correct 11 ms 24572 KB n=100
6 Correct 11 ms 24612 KB n=100
7 Correct 11 ms 24516 KB n=100
8 Correct 11 ms 24524 KB n=100
9 Correct 11 ms 24524 KB n=100
10 Correct 11 ms 24524 KB n=100
11 Correct 13 ms 24576 KB n=100
12 Correct 11 ms 24524 KB n=100
13 Correct 11 ms 24560 KB n=100
14 Correct 11 ms 24524 KB n=100
15 Correct 11 ms 24616 KB n=100
16 Correct 12 ms 24652 KB n=100
17 Correct 12 ms 24524 KB n=100
18 Correct 11 ms 24552 KB n=100
19 Correct 13 ms 24564 KB n=100
20 Correct 11 ms 24524 KB n=100
21 Correct 11 ms 24588 KB n=100
22 Correct 12 ms 24576 KB n=100
23 Correct 10 ms 24524 KB n=100
24 Correct 11 ms 24524 KB n=100
25 Correct 11 ms 24524 KB n=100
26 Correct 10 ms 24568 KB n=12
27 Correct 11 ms 24572 KB n=100
28 Correct 12 ms 24668 KB n=500
29 Correct 11 ms 24772 KB n=500
30 Correct 12 ms 24728 KB n=500
31 Correct 12 ms 24692 KB n=500
32 Correct 12 ms 24780 KB n=500
33 Correct 12 ms 24716 KB n=500
34 Correct 12 ms 24652 KB n=500
35 Correct 12 ms 24652 KB n=500
36 Correct 12 ms 24652 KB n=500
37 Correct 12 ms 24692 KB n=500
38 Correct 14 ms 24700 KB n=500
39 Correct 14 ms 24652 KB n=500
40 Correct 11 ms 24652 KB n=500
41 Correct 11 ms 24636 KB n=500
42 Correct 12 ms 24708 KB n=500
43 Correct 12 ms 24612 KB n=500
44 Correct 12 ms 24708 KB n=500
45 Correct 12 ms 24712 KB n=500
46 Correct 12 ms 24732 KB n=500
47 Correct 12 ms 24652 KB n=500
48 Correct 12 ms 24652 KB n=500
49 Correct 11 ms 24712 KB n=500
50 Correct 15 ms 24644 KB n=500
51 Correct 13 ms 24632 KB n=500
52 Correct 12 ms 24708 KB n=500
53 Correct 12 ms 24716 KB n=500
54 Correct 11 ms 24652 KB n=500
55 Correct 11 ms 24652 KB n=278
56 Correct 13 ms 24652 KB n=500
57 Correct 14 ms 24700 KB n=500
58 Correct 11 ms 24652 KB n=500
59 Correct 15 ms 25100 KB n=2000
60 Correct 16 ms 25052 KB n=2000
61 Correct 17 ms 25036 KB n=2000
62 Correct 14 ms 25092 KB n=2000
63 Correct 14 ms 25036 KB n=2000
64 Correct 16 ms 25052 KB n=2000
65 Correct 14 ms 25064 KB n=2000
66 Correct 17 ms 25036 KB n=2000
67 Correct 14 ms 25036 KB n=2000
68 Correct 14 ms 25092 KB n=2000
69 Correct 14 ms 25036 KB n=2000
70 Correct 14 ms 25036 KB n=2000
71 Correct 14 ms 25028 KB n=2000
72 Correct 13 ms 25036 KB n=2000
73 Correct 17 ms 25024 KB n=2000
74 Correct 15 ms 25024 KB n=1844
75 Correct 18 ms 25096 KB n=2000
76 Correct 16 ms 25076 KB n=2000
77 Correct 17 ms 25096 KB n=2000
78 Correct 16 ms 25028 KB n=2000
79 Correct 16 ms 25080 KB n=2000
80 Correct 14 ms 25060 KB n=2000
81 Correct 14 ms 25100 KB n=2000
82 Correct 14 ms 25036 KB n=2000
83 Correct 13 ms 25020 KB n=2000
84 Correct 14 ms 25036 KB n=2000
85 Correct 13 ms 25060 KB n=2000
86 Correct 14 ms 25052 KB n=2000
87 Correct 14 ms 25044 KB n=2000
88 Correct 14 ms 25056 KB n=2000
89 Correct 14 ms 25036 KB n=2000
90 Correct 14 ms 25028 KB n=2000
91 Correct 14 ms 25092 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24524 KB n=5
2 Correct 11 ms 24524 KB n=100
3 Correct 11 ms 24524 KB n=100
4 Correct 11 ms 24524 KB n=100
5 Correct 11 ms 24572 KB n=100
6 Correct 11 ms 24612 KB n=100
7 Correct 11 ms 24516 KB n=100
8 Correct 11 ms 24524 KB n=100
9 Correct 11 ms 24524 KB n=100
10 Correct 11 ms 24524 KB n=100
11 Correct 13 ms 24576 KB n=100
12 Correct 11 ms 24524 KB n=100
13 Correct 11 ms 24560 KB n=100
14 Correct 11 ms 24524 KB n=100
15 Correct 11 ms 24616 KB n=100
16 Correct 12 ms 24652 KB n=100
17 Correct 12 ms 24524 KB n=100
18 Correct 11 ms 24552 KB n=100
19 Correct 13 ms 24564 KB n=100
20 Correct 11 ms 24524 KB n=100
21 Correct 11 ms 24588 KB n=100
22 Correct 12 ms 24576 KB n=100
23 Correct 10 ms 24524 KB n=100
24 Correct 11 ms 24524 KB n=100
25 Correct 11 ms 24524 KB n=100
26 Correct 10 ms 24568 KB n=12
27 Correct 11 ms 24572 KB n=100
28 Correct 12 ms 24668 KB n=500
29 Correct 11 ms 24772 KB n=500
30 Correct 12 ms 24728 KB n=500
31 Correct 12 ms 24692 KB n=500
32 Correct 12 ms 24780 KB n=500
33 Correct 12 ms 24716 KB n=500
34 Correct 12 ms 24652 KB n=500
35 Correct 12 ms 24652 KB n=500
36 Correct 12 ms 24652 KB n=500
37 Correct 12 ms 24692 KB n=500
38 Correct 14 ms 24700 KB n=500
39 Correct 14 ms 24652 KB n=500
40 Correct 11 ms 24652 KB n=500
41 Correct 11 ms 24636 KB n=500
42 Correct 12 ms 24708 KB n=500
43 Correct 12 ms 24612 KB n=500
44 Correct 12 ms 24708 KB n=500
45 Correct 12 ms 24712 KB n=500
46 Correct 12 ms 24732 KB n=500
47 Correct 12 ms 24652 KB n=500
48 Correct 12 ms 24652 KB n=500
49 Correct 11 ms 24712 KB n=500
50 Correct 15 ms 24644 KB n=500
51 Correct 13 ms 24632 KB n=500
52 Correct 12 ms 24708 KB n=500
53 Correct 12 ms 24716 KB n=500
54 Correct 11 ms 24652 KB n=500
55 Correct 11 ms 24652 KB n=278
56 Correct 13 ms 24652 KB n=500
57 Correct 14 ms 24700 KB n=500
58 Correct 11 ms 24652 KB n=500
59 Correct 15 ms 25100 KB n=2000
60 Correct 16 ms 25052 KB n=2000
61 Correct 17 ms 25036 KB n=2000
62 Correct 14 ms 25092 KB n=2000
63 Correct 14 ms 25036 KB n=2000
64 Correct 16 ms 25052 KB n=2000
65 Correct 14 ms 25064 KB n=2000
66 Correct 17 ms 25036 KB n=2000
67 Correct 14 ms 25036 KB n=2000
68 Correct 14 ms 25092 KB n=2000
69 Correct 14 ms 25036 KB n=2000
70 Correct 14 ms 25036 KB n=2000
71 Correct 14 ms 25028 KB n=2000
72 Correct 13 ms 25036 KB n=2000
73 Correct 17 ms 25024 KB n=2000
74 Correct 15 ms 25024 KB n=1844
75 Correct 18 ms 25096 KB n=2000
76 Correct 16 ms 25076 KB n=2000
77 Correct 17 ms 25096 KB n=2000
78 Correct 16 ms 25028 KB n=2000
79 Correct 16 ms 25080 KB n=2000
80 Correct 14 ms 25060 KB n=2000
81 Correct 14 ms 25100 KB n=2000
82 Correct 14 ms 25036 KB n=2000
83 Correct 13 ms 25020 KB n=2000
84 Correct 14 ms 25036 KB n=2000
85 Correct 13 ms 25060 KB n=2000
86 Correct 14 ms 25052 KB n=2000
87 Correct 14 ms 25044 KB n=2000
88 Correct 14 ms 25056 KB n=2000
89 Correct 14 ms 25036 KB n=2000
90 Correct 14 ms 25028 KB n=2000
91 Correct 14 ms 25092 KB n=2000
92 Correct 629 ms 75536 KB n=200000
93 Correct 786 ms 78384 KB n=200000
94 Correct 747 ms 80380 KB n=200000
95 Correct 756 ms 75120 KB n=200000
96 Correct 635 ms 75260 KB n=200000
97 Correct 868 ms 77800 KB n=200000
98 Correct 641 ms 75160 KB n=200000
99 Correct 844 ms 75308 KB n=200000
100 Correct 624 ms 75132 KB n=200000
101 Correct 767 ms 81096 KB n=200000
102 Correct 469 ms 76336 KB n=200000
103 Correct 485 ms 76256 KB n=200000
104 Correct 505 ms 76272 KB n=200000
105 Correct 455 ms 76680 KB n=200000
106 Correct 510 ms 76680 KB n=200000
107 Correct 453 ms 76740 KB n=200000
108 Correct 763 ms 75280 KB n=200000
109 Correct 796 ms 75272 KB n=200000
110 Correct 732 ms 75204 KB n=200000
111 Correct 701 ms 74660 KB n=200000
112 Correct 749 ms 80384 KB n=200000
113 Correct 805 ms 77664 KB n=200000
114 Correct 684 ms 74608 KB n=200000
115 Correct 929 ms 76448 KB n=200000
116 Correct 582 ms 75404 KB n=200000
117 Correct 723 ms 80548 KB n=200000
118 Correct 810 ms 77008 KB n=200000
119 Correct 604 ms 75280 KB n=200000
120 Correct 738 ms 79856 KB n=200000
121 Correct 678 ms 80064 KB n=200000
122 Correct 728 ms 80304 KB n=200000
123 Correct 523 ms 76432 KB n=200000
124 Correct 186 ms 39016 KB n=25264