oj.uz

Submission #376514

# Submission time Handle Problem Language Result Execution time Memory
376514 2021-03-11T15:38:17 Z SeDunion Birthday gift (IZhO18_treearray) C++17
100 / 100
 1862 ms 179064 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

vector<int>g[N];

const int LOG = 20;

int tin[N], tout[N], up[LOG][N], timer;

void dfs(int v, int p = 1) {
	tin[v] = timer++;
	up[0][v] = p; for (int i = 1 ; i < LOG ; ++ i) up[i][v] = up[i - 1][up[i - 1][v]];
	for (int to : g[v]) if (to != p) {
		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 = LOG - 1 ; i >= 0 ; -- i) {
		if (!upper(up[i][a], b)) a = up[i][a];
	}
	return up[0][a];
}

int a[N];

set<int>pos1[N], pos2[N];

int main() {
	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 a, b;
		cin >> a >> b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	dfs(1);
	for (int i = 1 ; i <= m ; ++ i) {
		cin >> a[i];
		pos1[a[i]].insert(i);
		if (i > 1) {
			pos2[lca(a[i], a[i - 1])].insert(i);
		}
	}
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int i, v;
			cin >> i >> v;
			pos1[a[i]].erase(i);
			if (i > 1)
				pos2[lca(a[i], a[i - 1])].erase(i);
			if (i < m)
				pos2[lca(a[i], a[i + 1])].erase(i + 1);
			a[i] = v;
			pos1[a[i]].insert(i);
			if (i > 1)
				pos2[lca(a[i], a[i - 1])].insert(i);
			if (i < m)
				pos2[lca(a[i], a[i + 1])].insert(i + 1);
			continue;
		}
		int l, r, v;
		cin >> l >> r >> v;
		{
			auto it = pos1[v].lower_bound(l);
			if (pos1[v].end() != it && *it <= r) {
				cout << *it << " " << *it << "\n";
				continue;
			}
		}
		{
			auto it = pos2[v].upper_bound(l);
			if (pos2[v].end() != it && *it <= r) {
				cout << *it - 1 << " " << *it << "\n";
				continue;
			}
		}
		cout << "-1 -1\n";
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 117996 KB n=5
2 Correct 72 ms 117996 KB n=100
3 Correct 73 ms 117996 KB n=100
4 Correct 72 ms 117996 KB n=100
5 Correct 71 ms 117996 KB n=100
6 Correct 72 ms 117996 KB n=100
7 Correct 73 ms 117996 KB n=100
8 Correct 74 ms 117996 KB n=100
9 Correct 73 ms 118124 KB n=100
10 Correct 74 ms 117996 KB n=100
11 Correct 72 ms 118124 KB n=100
12 Correct 73 ms 117996 KB n=100
13 Correct 72 ms 117996 KB n=100
14 Correct 74 ms 117996 KB n=100
15 Correct 73 ms 118124 KB n=100
16 Correct 73 ms 117996 KB n=100
17 Correct 72 ms 117996 KB n=100
18 Correct 71 ms 117996 KB n=100
19 Correct 73 ms 118016 KB n=100
20 Correct 72 ms 118124 KB n=100
21 Correct 72 ms 117996 KB n=100
22 Correct 72 ms 117996 KB n=100
23 Correct 72 ms 117996 KB n=100
24 Correct 74 ms 117996 KB n=100
25 Correct 73 ms 117996 KB n=100
26 Correct 79 ms 118124 KB n=12
27 Correct 73 ms 117996 KB n=100
28 Correct 73 ms 117996 KB n=500
29 Correct 74 ms 118044 KB n=500
30 Correct 73 ms 118124 KB n=500
31 Correct 76 ms 118124 KB n=500
32 Correct 74 ms 117996 KB n=500
33 Correct 73 ms 118124 KB n=500
34 Correct 74 ms 118124 KB n=500
35 Correct 72 ms 118124 KB n=500
36 Correct 73 ms 118124 KB n=500
37 Correct 84 ms 117996 KB n=500
38 Correct 72 ms 117996 KB n=500
39 Correct 72 ms 118124 KB n=500
40 Correct 73 ms 117996 KB n=500
41 Correct 72 ms 117996 KB n=500
42 Correct 73 ms 118124 KB n=500
43 Correct 72 ms 117996 KB n=500
44 Correct 73 ms 117996 KB n=500
45 Correct 74 ms 117996 KB n=500
46 Correct 72 ms 118124 KB n=500
47 Correct 73 ms 118124 KB n=500
48 Correct 72 ms 117996 KB n=500
49 Correct 71 ms 118164 KB n=500
50 Correct 73 ms 117996 KB n=500
51 Correct 73 ms 118124 KB n=500
52 Correct 74 ms 118124 KB n=500
53 Correct 84 ms 117996 KB n=500
54 Correct 73 ms 118028 KB n=500
55 Correct 72 ms 118124 KB n=278
56 Correct 72 ms 118124 KB n=500
57 Correct 73 ms 118124 KB n=500
58 Correct 73 ms 117996 KB n=500
59 Correct 77 ms 118380 KB n=2000
60 Correct 76 ms 118508 KB n=2000
61 Correct 76 ms 118380 KB n=2000
62 Correct 77 ms 118380 KB n=2000
63 Correct 77 ms 118380 KB n=2000
64 Correct 76 ms 118472 KB n=2000
65 Correct 79 ms 118380 KB n=2000
66 Correct 87 ms 118508 KB n=2000
67 Correct 76 ms 118380 KB n=2000
68 Correct 76 ms 118380 KB n=2000
69 Correct 75 ms 118380 KB n=2000
70 Correct 77 ms 118636 KB n=2000
71 Correct 75 ms 118380 KB n=2000
72 Correct 78 ms 118380 KB n=2000
73 Correct 75 ms 118380 KB n=2000
74 Correct 77 ms 118380 KB n=1844
75 Correct 76 ms 118380 KB n=2000
76 Correct 78 ms 118508 KB n=2000
77 Correct 85 ms 118380 KB n=2000
78 Correct 78 ms 118380 KB n=2000
79 Correct 78 ms 118508 KB n=2000
80 Correct 77 ms 118508 KB n=2000
81 Correct 77 ms 118380 KB n=2000
82 Correct 78 ms 118380 KB n=2000
83 Correct 76 ms 118620 KB n=2000
84 Correct 81 ms 118380 KB n=2000
85 Correct 76 ms 118380 KB n=2000
86 Correct 75 ms 118508 KB n=2000
87 Correct 77 ms 118380 KB n=2000
88 Correct 84 ms 118508 KB n=2000
89 Correct 78 ms 118508 KB n=2000
90 Correct 76 ms 118508 KB n=2000
91 Correct 77 ms 118380 KB n=2000
92 Correct 1776 ms 163180 KB n=200000
93 Correct 1299 ms 174572 KB n=200000
94 Correct 833 ms 177900 KB n=200000
95 Correct 1814 ms 169628 KB n=200000
96 Correct 1755 ms 169536 KB n=200000
97 Correct 1467 ms 173696 KB n=200000
98 Correct 1793 ms 169488 KB n=200000
99 Correct 1821 ms 169800 KB n=200000
100 Correct 1782 ms 169652 KB n=200000
101 Correct 707 ms 179064 KB n=200000
102 Correct 953 ms 170604 KB n=200000
103 Correct 917 ms 170616 KB n=200000
104 Correct 883 ms 170604 KB n=200000
105 Correct 885 ms 170988 KB n=200000
106 Correct 915 ms 170892 KB n=200000
107 Correct 917 ms 170936 KB n=200000
108 Correct 1710 ms 169536 KB n=200000
109 Correct 1668 ms 169568 KB n=200000
110 Correct 1684 ms 169368 KB n=200000
111 Correct 1604 ms 168932 KB n=200000
112 Correct 794 ms 178104 KB n=200000
113 Correct 1410 ms 173736 KB n=200000
114 Correct 1584 ms 169004 KB n=200000
115 Correct 1862 ms 171500 KB n=200000
116 Correct 1779 ms 169440 KB n=200000
117 Correct 720 ms 178412 KB n=200000
118 Correct 1680 ms 172668 KB n=200000
119 Correct 1760 ms 169440 KB n=200000
120 Correct 628 ms 178028 KB n=200000
121 Correct 614 ms 178028 KB n=200000
122 Correct 637 ms 178540 KB n=200000
123 Correct 910 ms 170860 KB n=200000
124 Correct 303 ms 132972 KB n=25264