oj.uz

Submission #882656

# Submission time Handle Problem Language Result Execution time Memory
882656 2023-12-03T12:44:21 Z NintsiChkhaidze Birthday gift (IZhO18_treearray) C++17
100 / 100
 1341 ms 83244 KB 
#include <bits/stdc++.h>
#define s second
#define f first
#define ll long long
#define pb push_back
#define pii pair <int,int>
using namespace std;

const int N = 2e5 + 5;
int dp[N],d[25][N],arr[N];
vector <int> v[N];
multiset <int> vec[N],st[N];

void dfs(int x,int par){
	d[0][x] = par;
	dp[x] = dp[par] + 1;
	for (int to: v[x])
		if (to != par) dfs(to,x);
}

int lca(int x,int y){
	if (dp[x] < dp[y]) swap(x,y);
	for (int i = 18; i >= 0; i--)
		if (dp[d[i][x]] >= dp[y]) x = d[i][x];

	if (x == y) return x;
	for (int i = 18; i >= 0; i--)
		if (d[i][x] != d[i][y]) x = d[i][x], y = d[i][y];

	return d[0][x];
}

void upd(int idx,int p){
	int x = arr[idx],y = arr[idx + 1];
	int c = lca(x,y);

	if (!p) vec[c].erase(vec[c].find(idx));
	else vec[c].insert(idx);
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,m,q;
	cin>>n>>m>>q;

	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}

	for (int i = 1; i <= m; i++)
		cin >> arr[i],st[arr[i]].insert(i);

	dfs(1,1);
	for (int j = 1; j <= 18; j++)
		for (int i = 1; i <= n; i++)
			d[j][i] = d[j - 1][d[j - 1][i]];

	for (int i = 1; i < m; i++){
		int c = lca(arr[i],arr[i + 1]);
		vec[c].insert(i);
	}

	while (q--){
		int tp;
		cin>>tp;

		if (tp == 1){
			int pos,val;
			cin>>pos>>val;

			st[arr[pos]].erase(st[arr[pos]].find(pos));
			st[val].insert(pos);

			if (pos - 1 >= 1 && pos - 1 < m) upd(pos-1,0);
			if (pos >= 1 && pos < m) upd(pos,0);

			arr[pos] = val;
			
			if (pos - 1 >= 1 && pos - 1 < m) upd(pos-1,1);
			if (pos >= 1 && pos < m) upd(pos,1);
		}else{
			int l,r,x;
			cin>>l>>r>>x;

			multiset <int> :: iterator it;
			if (st[x].size()){
				it = st[x].lower_bound(l);
				if (it != st[x].end() && (*it) <= r){
					cout<<(*it)<<" "<<(*it)<<endl;
					continue;
				}
			}

			if (vec[x].size()){
				it = vec[x].lower_bound(l);
				if (it != vec[x].end() && (*it) < r){
					cout<<*it<<" "<<(*it) + 1<<endl;
					continue;
				}
			}
			cout<<-1<<" "<<-1<<endl;
		}
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39512 KB n=5
2 Correct 7 ms 39516 KB n=100
3 Correct 8 ms 39516 KB n=100
4 Correct 7 ms 39524 KB n=100
5 Correct 7 ms 39516 KB n=100
6 Correct 7 ms 39516 KB n=100
7 Correct 8 ms 39516 KB n=100
8 Correct 8 ms 39512 KB n=100
9 Correct 7 ms 39512 KB n=100
10 Correct 8 ms 39516 KB n=100
11 Correct 7 ms 39516 KB n=100
12 Correct 7 ms 39512 KB n=100
13 Correct 7 ms 39668 KB n=100
14 Correct 7 ms 39628 KB n=100
15 Correct 8 ms 39512 KB n=100
16 Correct 7 ms 39512 KB n=100
17 Correct 7 ms 39516 KB n=100
18 Correct 7 ms 39516 KB n=100
19 Correct 7 ms 39516 KB n=100
20 Correct 7 ms 39616 KB n=100
21 Correct 7 ms 39512 KB n=100
22 Correct 7 ms 39516 KB n=100
23 Correct 7 ms 39516 KB n=100
24 Correct 8 ms 39516 KB n=100
25 Correct 7 ms 39516 KB n=100
26 Correct 7 ms 39604 KB n=12
27 Correct 7 ms 39516 KB n=100
28 Correct 8 ms 39516 KB n=500
29 Correct 8 ms 39516 KB n=500
30 Correct 8 ms 39512 KB n=500
31 Correct 8 ms 39512 KB n=500
32 Correct 8 ms 39516 KB n=500
33 Correct 8 ms 39512 KB n=500
34 Correct 8 ms 39596 KB n=500
35 Correct 8 ms 39516 KB n=500
36 Correct 8 ms 39516 KB n=500
37 Correct 8 ms 39516 KB n=500
38 Correct 8 ms 39600 KB n=500
39 Correct 8 ms 39516 KB n=500
40 Correct 8 ms 39512 KB n=500
41 Correct 8 ms 39768 KB n=500
42 Correct 8 ms 39516 KB n=500
43 Correct 9 ms 39516 KB n=500
44 Correct 8 ms 39516 KB n=500
45 Correct 8 ms 39516 KB n=500
46 Correct 8 ms 39516 KB n=500
47 Correct 9 ms 39512 KB n=500
48 Correct 8 ms 39516 KB n=500
49 Correct 8 ms 39768 KB n=500
50 Correct 8 ms 39604 KB n=500
51 Correct 8 ms 39772 KB n=500
52 Correct 8 ms 39516 KB n=500
53 Correct 8 ms 39512 KB n=500
54 Correct 8 ms 39516 KB n=500
55 Correct 7 ms 39516 KB n=278
56 Correct 8 ms 39516 KB n=500
57 Correct 9 ms 39516 KB n=500
58 Correct 8 ms 39516 KB n=500
59 Correct 11 ms 39768 KB n=2000
60 Correct 11 ms 40028 KB n=2000
61 Correct 11 ms 39768 KB n=2000
62 Correct 12 ms 40024 KB n=2000
63 Correct 11 ms 39860 KB n=2000
64 Correct 11 ms 39808 KB n=2000
65 Correct 11 ms 39772 KB n=2000
66 Correct 11 ms 39772 KB n=2000
67 Correct 13 ms 39768 KB n=2000
68 Correct 11 ms 39768 KB n=2000
69 Correct 14 ms 39772 KB n=2000
70 Correct 11 ms 39772 KB n=2000
71 Correct 11 ms 39772 KB n=2000
72 Correct 11 ms 39968 KB n=2000
73 Correct 11 ms 40024 KB n=2000
74 Correct 10 ms 39772 KB n=1844
75 Correct 11 ms 39772 KB n=2000
76 Correct 12 ms 39780 KB n=2000
77 Correct 12 ms 39772 KB n=2000
78 Correct 11 ms 39772 KB n=2000
79 Correct 11 ms 39772 KB n=2000
80 Correct 12 ms 39968 KB n=2000
81 Correct 11 ms 39768 KB n=2000
82 Correct 11 ms 39772 KB n=2000
83 Correct 12 ms 39988 KB n=2000
84 Correct 11 ms 39772 KB n=2000
85 Correct 11 ms 39772 KB n=2000
86 Correct 11 ms 39804 KB n=2000
87 Correct 11 ms 39772 KB n=2000
88 Correct 10 ms 40028 KB n=2000
89 Correct 10 ms 40028 KB n=2000
90 Correct 10 ms 40028 KB n=2000
91 Correct 12 ms 39768 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39512 KB n=5
2 Correct 7 ms 39516 KB n=100
3 Correct 8 ms 39516 KB n=100
4 Correct 7 ms 39524 KB n=100
5 Correct 7 ms 39516 KB n=100
6 Correct 7 ms 39516 KB n=100
7 Correct 8 ms 39516 KB n=100
8 Correct 8 ms 39512 KB n=100
9 Correct 7 ms 39512 KB n=100
10 Correct 8 ms 39516 KB n=100
11 Correct 7 ms 39516 KB n=100
12 Correct 7 ms 39512 KB n=100
13 Correct 7 ms 39668 KB n=100
14 Correct 7 ms 39628 KB n=100
15 Correct 8 ms 39512 KB n=100
16 Correct 7 ms 39512 KB n=100
17 Correct 7 ms 39516 KB n=100
18 Correct 7 ms 39516 KB n=100
19 Correct 7 ms 39516 KB n=100
20 Correct 7 ms 39616 KB n=100
21 Correct 7 ms 39512 KB n=100
22 Correct 7 ms 39516 KB n=100
23 Correct 7 ms 39516 KB n=100
24 Correct 8 ms 39516 KB n=100
25 Correct 7 ms 39516 KB n=100
26 Correct 7 ms 39604 KB n=12
27 Correct 7 ms 39516 KB n=100
28 Correct 8 ms 39516 KB n=500
29 Correct 8 ms 39516 KB n=500
30 Correct 8 ms 39512 KB n=500
31 Correct 8 ms 39512 KB n=500
32 Correct 8 ms 39516 KB n=500
33 Correct 8 ms 39512 KB n=500
34 Correct 8 ms 39596 KB n=500
35 Correct 8 ms 39516 KB n=500
36 Correct 8 ms 39516 KB n=500
37 Correct 8 ms 39516 KB n=500
38 Correct 8 ms 39600 KB n=500
39 Correct 8 ms 39516 KB n=500
40 Correct 8 ms 39512 KB n=500
41 Correct 8 ms 39768 KB n=500
42 Correct 8 ms 39516 KB n=500
43 Correct 9 ms 39516 KB n=500
44 Correct 8 ms 39516 KB n=500
45 Correct 8 ms 39516 KB n=500
46 Correct 8 ms 39516 KB n=500
47 Correct 9 ms 39512 KB n=500
48 Correct 8 ms 39516 KB n=500
49 Correct 8 ms 39768 KB n=500
50 Correct 8 ms 39604 KB n=500
51 Correct 8 ms 39772 KB n=500
52 Correct 8 ms 39516 KB n=500
53 Correct 8 ms 39512 KB n=500
54 Correct 8 ms 39516 KB n=500
55 Correct 7 ms 39516 KB n=278
56 Correct 8 ms 39516 KB n=500
57 Correct 9 ms 39516 KB n=500
58 Correct 8 ms 39516 KB n=500
59 Correct 11 ms 39768 KB n=2000
60 Correct 11 ms 40028 KB n=2000
61 Correct 11 ms 39768 KB n=2000
62 Correct 12 ms 40024 KB n=2000
63 Correct 11 ms 39860 KB n=2000
64 Correct 11 ms 39808 KB n=2000
65 Correct 11 ms 39772 KB n=2000
66 Correct 11 ms 39772 KB n=2000
67 Correct 13 ms 39768 KB n=2000
68 Correct 11 ms 39768 KB n=2000
69 Correct 14 ms 39772 KB n=2000
70 Correct 11 ms 39772 KB n=2000
71 Correct 11 ms 39772 KB n=2000
72 Correct 11 ms 39968 KB n=2000
73 Correct 11 ms 40024 KB n=2000
74 Correct 10 ms 39772 KB n=1844
75 Correct 11 ms 39772 KB n=2000
76 Correct 12 ms 39780 KB n=2000
77 Correct 12 ms 39772 KB n=2000
78 Correct 11 ms 39772 KB n=2000
79 Correct 11 ms 39772 KB n=2000
80 Correct 12 ms 39968 KB n=2000
81 Correct 11 ms 39768 KB n=2000
82 Correct 11 ms 39772 KB n=2000
83 Correct 12 ms 39988 KB n=2000
84 Correct 11 ms 39772 KB n=2000
85 Correct 11 ms 39772 KB n=2000
86 Correct 11 ms 39804 KB n=2000
87 Correct 11 ms 39772 KB n=2000
88 Correct 10 ms 40028 KB n=2000
89 Correct 10 ms 40028 KB n=2000
90 Correct 10 ms 40028 KB n=2000
91 Correct 12 ms 39768 KB n=2000
92 Correct 867 ms 73840 KB n=200000
93 Correct 1130 ms 78788 KB n=200000
94 Correct 1186 ms 81924 KB n=200000
95 Correct 882 ms 73620 KB n=200000
96 Correct 912 ms 73760 KB n=200000
97 Correct 1241 ms 78000 KB n=200000
98 Correct 940 ms 73748 KB n=200000
99 Correct 1049 ms 73912 KB n=200000
100 Correct 945 ms 73828 KB n=200000
101 Correct 1058 ms 83244 KB n=200000
102 Correct 524 ms 74692 KB n=200000
103 Correct 565 ms 74896 KB n=200000
104 Correct 526 ms 75036 KB n=200000
105 Correct 555 ms 75220 KB n=200000
106 Correct 582 ms 75344 KB n=200000
107 Correct 603 ms 75204 KB n=200000
108 Correct 957 ms 73672 KB n=200000
109 Correct 1025 ms 73616 KB n=200000
110 Correct 1036 ms 73828 KB n=200000
111 Correct 827 ms 73160 KB n=200000
112 Correct 1165 ms 82284 KB n=200000
113 Correct 1202 ms 77724 KB n=200000
114 Correct 922 ms 73448 KB n=200000
115 Correct 1341 ms 75964 KB n=200000
116 Correct 864 ms 73744 KB n=200000
117 Correct 1134 ms 82844 KB n=200000
118 Correct 1272 ms 76732 KB n=200000
119 Correct 737 ms 73816 KB n=200000
120 Correct 1075 ms 82332 KB n=200000
121 Correct 1070 ms 82564 KB n=200000
122 Correct 1051 ms 82796 KB n=200000
123 Correct 514 ms 75120 KB n=200000
124 Correct 193 ms 52052 KB n=25264