oj.uz

Submission #685161

# Submission time Handle Problem Language Result Execution time Memory
685161 2023-01-23T15:53:01 Z Nuraly_Serikbay Birthday gift (IZhO18_treearray) C++14
100 / 100
 1317 ms 123236 KB 
/* Speech to the young */

//#include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
/*
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse,-fgcse-lm")
#pragma GCC optimize("-ftree-pre,-ftree-vrp")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
*/
 

using namespace std;

#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)
#define int long long
#define cube (x) ((x) * (x) * (x))

int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
void pre(int a) { cout<<fixed<<setprecision(a); }
int bitcount (int x) {return __builtin_popcount	(x);}

const int N = 2e5 + 10;
const int INF = 1e18 + 1;
const int MOD = 1e9 + 7;
const int P = 31;
const double eps = 1e-19;
long double pi = 3.1415926535897323;

int n, m, q, depth[N], up[N][22], a[N];
vector <int> g[N];
set <int> sg[N], tw[N];

void dfs (int v, int p) {
	up[v][0] = p;
	for (int i = 1; i <= 20; ++ i) up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto to: g[v]) {
		if (to != p) {
			depth[to] = depth[v] + 1;
			dfs (to, v);
		}
	}
	return;
}

int lca (int a, int b) {
	if (depth[a] < depth[b]) swap (a, b);
	int k = depth[a] - depth[b];
	for (int i = 20; i >= 0; -- i) if (((k >> i) & 1)) a = up[a][i];
	if (a == b) return a;
	for (int i = 20; i >= 0; -- i) {
		if (up[a][i] != up[b][i]) {
			a = up[a][i], b = up[b][i];
		}
	}
	return up[a][0];
} 


void Solution () {
	cin >> n >> m >> q;
	int x, y;
	for (int i = 1; i < n; ++ i) {
		cin >> x >> y;
		g[x].pb (y), g[y].pb (x);
	}
	dfs (1, 0);
	for (int i = 1; i <= m; ++ i) {
		cin >> a[i];
		sg[a[i]].insert (i);
	}
	for (int i = 1; i < m; ++ i) {
		int x = lca (a[i], a[i + 1]);
		tw[x].insert (i);
	}
	while (q --) {
		int tp, l, r, v, pos;
		cin >> tp;
		if (tp == 1) {
			cin >> pos >> v;
			sg[a[pos]].erase (pos);
			if (pos < m) tw[lca (a[pos], a[pos + 1])].erase (pos);
			if (pos > 1) tw[lca (a[pos], a[pos - 1])].erase (pos - 1);
			a[pos] = v;
			sg[v].insert (pos);
			if (pos < m) tw[lca (a[pos], a[pos + 1])].insert (pos);
			if (pos > 1) tw[lca (a[pos], a[pos - 1])].insert (pos - 1);
			
		} else {
			cin >> l >> r >> v;
			int x = *sg[v].lower_bound (l);
			if (x <= r) {
				cout << x << ' ' << x << '\n';
				continue;
			}
			x = *tw[v].lower_bound (l);
		//	cout << x << ' ';
			if (x < r) {
				cout << x << ' ' << x + 1 << '\n';
				continue;
			}
			cout << "-1 -1\n";	
		}
	}
	
}

signed main () {
	YOSIK();
//	precalc();
	int T = 1;
//	cin >> T;
	for (int i = 1; i < N; ++ i) sg[i].insert (INF), tw[i].insert (INF);
	
	while (T --) Solution ();
	exit (0);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 42580 KB n=5
2 Correct 35 ms 42632 KB n=100
3 Correct 36 ms 42572 KB n=100
4 Correct 33 ms 42632 KB n=100
5 Correct 36 ms 42700 KB n=100
6 Correct 39 ms 42552 KB n=100
7 Correct 35 ms 42576 KB n=100
8 Correct 34 ms 42604 KB n=100
9 Correct 34 ms 42636 KB n=100
10 Correct 37 ms 42600 KB n=100
11 Correct 36 ms 42564 KB n=100
12 Correct 34 ms 42576 KB n=100
13 Correct 33 ms 42580 KB n=100
14 Correct 33 ms 42612 KB n=100
15 Correct 34 ms 42560 KB n=100
16 Correct 37 ms 42580 KB n=100
17 Correct 36 ms 42700 KB n=100
18 Correct 41 ms 42572 KB n=100
19 Correct 35 ms 42572 KB n=100
20 Correct 33 ms 42584 KB n=100
21 Correct 43 ms 42572 KB n=100
22 Correct 42 ms 42636 KB n=100
23 Correct 34 ms 42580 KB n=100
24 Correct 34 ms 42580 KB n=100
25 Correct 36 ms 42728 KB n=100
26 Correct 35 ms 42584 KB n=12
27 Correct 35 ms 42640 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 42580 KB n=5
2 Correct 35 ms 42632 KB n=100
3 Correct 36 ms 42572 KB n=100
4 Correct 33 ms 42632 KB n=100
5 Correct 36 ms 42700 KB n=100
6 Correct 39 ms 42552 KB n=100
7 Correct 35 ms 42576 KB n=100
8 Correct 34 ms 42604 KB n=100
9 Correct 34 ms 42636 KB n=100
10 Correct 37 ms 42600 KB n=100
11 Correct 36 ms 42564 KB n=100
12 Correct 34 ms 42576 KB n=100
13 Correct 33 ms 42580 KB n=100
14 Correct 33 ms 42612 KB n=100
15 Correct 34 ms 42560 KB n=100
16 Correct 37 ms 42580 KB n=100
17 Correct 36 ms 42700 KB n=100
18 Correct 41 ms 42572 KB n=100
19 Correct 35 ms 42572 KB n=100
20 Correct 33 ms 42584 KB n=100
21 Correct 43 ms 42572 KB n=100
22 Correct 42 ms 42636 KB n=100
23 Correct 34 ms 42580 KB n=100
24 Correct 34 ms 42580 KB n=100
25 Correct 36 ms 42728 KB n=100
26 Correct 35 ms 42584 KB n=12
27 Correct 35 ms 42640 KB n=100
28 Correct 35 ms 42780 KB n=500
29 Correct 34 ms 42740 KB n=500
30 Correct 41 ms 42700 KB n=500
31 Correct 35 ms 42756 KB n=500
32 Correct 35 ms 42724 KB n=500
33 Correct 35 ms 42692 KB n=500
34 Correct 35 ms 42712 KB n=500
35 Correct 40 ms 42700 KB n=500
36 Correct 37 ms 42748 KB n=500
37 Correct 35 ms 42896 KB n=500
38 Correct 35 ms 42712 KB n=500
39 Correct 35 ms 42680 KB n=500
40 Correct 33 ms 42728 KB n=500
41 Correct 34 ms 42780 KB n=500
42 Correct 34 ms 42772 KB n=500
43 Correct 34 ms 42684 KB n=500
44 Correct 38 ms 42796 KB n=500
45 Correct 37 ms 42684 KB n=500
46 Correct 42 ms 42668 KB n=500
47 Correct 34 ms 42684 KB n=500
48 Correct 35 ms 42676 KB n=500
49 Correct 34 ms 42712 KB n=500
50 Correct 45 ms 42776 KB n=500
51 Correct 36 ms 42764 KB n=500
52 Correct 34 ms 42756 KB n=500
53 Correct 35 ms 42748 KB n=500
54 Correct 36 ms 42760 KB n=500
55 Correct 35 ms 42704 KB n=278
56 Correct 34 ms 42728 KB n=500
57 Correct 34 ms 42732 KB n=500
58 Correct 35 ms 42772 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 42580 KB n=5
2 Correct 35 ms 42632 KB n=100
3 Correct 36 ms 42572 KB n=100
4 Correct 33 ms 42632 KB n=100
5 Correct 36 ms 42700 KB n=100
6 Correct 39 ms 42552 KB n=100
7 Correct 35 ms 42576 KB n=100
8 Correct 34 ms 42604 KB n=100
9 Correct 34 ms 42636 KB n=100
10 Correct 37 ms 42600 KB n=100
11 Correct 36 ms 42564 KB n=100
12 Correct 34 ms 42576 KB n=100
13 Correct 33 ms 42580 KB n=100
14 Correct 33 ms 42612 KB n=100
15 Correct 34 ms 42560 KB n=100
16 Correct 37 ms 42580 KB n=100
17 Correct 36 ms 42700 KB n=100
18 Correct 41 ms 42572 KB n=100
19 Correct 35 ms 42572 KB n=100
20 Correct 33 ms 42584 KB n=100
21 Correct 43 ms 42572 KB n=100
22 Correct 42 ms 42636 KB n=100
23 Correct 34 ms 42580 KB n=100
24 Correct 34 ms 42580 KB n=100
25 Correct 36 ms 42728 KB n=100
26 Correct 35 ms 42584 KB n=12
27 Correct 35 ms 42640 KB n=100
28 Correct 35 ms 42780 KB n=500
29 Correct 34 ms 42740 KB n=500
30 Correct 41 ms 42700 KB n=500
31 Correct 35 ms 42756 KB n=500
32 Correct 35 ms 42724 KB n=500
33 Correct 35 ms 42692 KB n=500
34 Correct 35 ms 42712 KB n=500
35 Correct 40 ms 42700 KB n=500
36 Correct 37 ms 42748 KB n=500
37 Correct 35 ms 42896 KB n=500
38 Correct 35 ms 42712 KB n=500
39 Correct 35 ms 42680 KB n=500
40 Correct 33 ms 42728 KB n=500
41 Correct 34 ms 42780 KB n=500
42 Correct 34 ms 42772 KB n=500
43 Correct 34 ms 42684 KB n=500
44 Correct 38 ms 42796 KB n=500
45 Correct 37 ms 42684 KB n=500
46 Correct 42 ms 42668 KB n=500
47 Correct 34 ms 42684 KB n=500
48 Correct 35 ms 42676 KB n=500
49 Correct 34 ms 42712 KB n=500
50 Correct 45 ms 42776 KB n=500
51 Correct 36 ms 42764 KB n=500
52 Correct 34 ms 42756 KB n=500
53 Correct 35 ms 42748 KB n=500
54 Correct 36 ms 42760 KB n=500
55 Correct 35 ms 42704 KB n=278
56 Correct 34 ms 42728 KB n=500
57 Correct 34 ms 42732 KB n=500
58 Correct 35 ms 42772 KB n=500
59 Correct 44 ms 43308 KB n=2000
60 Correct 37 ms 43340 KB n=2000
61 Correct 40 ms 43244 KB n=2000
62 Correct 38 ms 43232 KB n=2000
63 Correct 42 ms 43300 KB n=2000
64 Correct 37 ms 43328 KB n=2000
65 Correct 39 ms 43192 KB n=2000
66 Correct 37 ms 43356 KB n=2000
67 Correct 37 ms 43208 KB n=2000
68 Correct 37 ms 43212 KB n=2000
69 Correct 37 ms 43340 KB n=2000
70 Correct 41 ms 43236 KB n=2000
71 Correct 39 ms 43204 KB n=2000
72 Correct 37 ms 43196 KB n=2000
73 Correct 36 ms 43268 KB n=2000
74 Correct 42 ms 43184 KB n=1844
75 Correct 38 ms 43344 KB n=2000
76 Correct 40 ms 43200 KB n=2000
77 Correct 38 ms 43312 KB n=2000
78 Correct 36 ms 43216 KB n=2000
79 Correct 37 ms 43244 KB n=2000
80 Correct 38 ms 43276 KB n=2000
81 Correct 37 ms 43312 KB n=2000
82 Correct 37 ms 43300 KB n=2000
83 Correct 40 ms 43316 KB n=2000
84 Correct 39 ms 43212 KB n=2000
85 Correct 45 ms 43324 KB n=2000
86 Correct 40 ms 43236 KB n=2000
87 Correct 37 ms 43216 KB n=2000
88 Correct 40 ms 43380 KB n=2000
89 Correct 37 ms 43352 KB n=2000
90 Correct 39 ms 43372 KB n=2000
91 Correct 47 ms 43300 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 42580 KB n=5
2 Correct 35 ms 42632 KB n=100
3 Correct 36 ms 42572 KB n=100
4 Correct 33 ms 42632 KB n=100
5 Correct 36 ms 42700 KB n=100
6 Correct 39 ms 42552 KB n=100
7 Correct 35 ms 42576 KB n=100
8 Correct 34 ms 42604 KB n=100
9 Correct 34 ms 42636 KB n=100
10 Correct 37 ms 42600 KB n=100
11 Correct 36 ms 42564 KB n=100
12 Correct 34 ms 42576 KB n=100
13 Correct 33 ms 42580 KB n=100
14 Correct 33 ms 42612 KB n=100
15 Correct 34 ms 42560 KB n=100
16 Correct 37 ms 42580 KB n=100
17 Correct 36 ms 42700 KB n=100
18 Correct 41 ms 42572 KB n=100
19 Correct 35 ms 42572 KB n=100
20 Correct 33 ms 42584 KB n=100
21 Correct 43 ms 42572 KB n=100
22 Correct 42 ms 42636 KB n=100
23 Correct 34 ms 42580 KB n=100
24 Correct 34 ms 42580 KB n=100
25 Correct 36 ms 42728 KB n=100
26 Correct 35 ms 42584 KB n=12
27 Correct 35 ms 42640 KB n=100
28 Correct 35 ms 42780 KB n=500
29 Correct 34 ms 42740 KB n=500
30 Correct 41 ms 42700 KB n=500
31 Correct 35 ms 42756 KB n=500
32 Correct 35 ms 42724 KB n=500
33 Correct 35 ms 42692 KB n=500
34 Correct 35 ms 42712 KB n=500
35 Correct 40 ms 42700 KB n=500
36 Correct 37 ms 42748 KB n=500
37 Correct 35 ms 42896 KB n=500
38 Correct 35 ms 42712 KB n=500
39 Correct 35 ms 42680 KB n=500
40 Correct 33 ms 42728 KB n=500
41 Correct 34 ms 42780 KB n=500
42 Correct 34 ms 42772 KB n=500
43 Correct 34 ms 42684 KB n=500
44 Correct 38 ms 42796 KB n=500
45 Correct 37 ms 42684 KB n=500
46 Correct 42 ms 42668 KB n=500
47 Correct 34 ms 42684 KB n=500
48 Correct 35 ms 42676 KB n=500
49 Correct 34 ms 42712 KB n=500
50 Correct 45 ms 42776 KB n=500
51 Correct 36 ms 42764 KB n=500
52 Correct 34 ms 42756 KB n=500
53 Correct 35 ms 42748 KB n=500
54 Correct 36 ms 42760 KB n=500
55 Correct 35 ms 42704 KB n=278
56 Correct 34 ms 42728 KB n=500
57 Correct 34 ms 42732 KB n=500
58 Correct 35 ms 42772 KB n=500
59 Correct 44 ms 43308 KB n=2000
60 Correct 37 ms 43340 KB n=2000
61 Correct 40 ms 43244 KB n=2000
62 Correct 38 ms 43232 KB n=2000
63 Correct 42 ms 43300 KB n=2000
64 Correct 37 ms 43328 KB n=2000
65 Correct 39 ms 43192 KB n=2000
66 Correct 37 ms 43356 KB n=2000
67 Correct 37 ms 43208 KB n=2000
68 Correct 37 ms 43212 KB n=2000
69 Correct 37 ms 43340 KB n=2000
70 Correct 41 ms 43236 KB n=2000
71 Correct 39 ms 43204 KB n=2000
72 Correct 37 ms 43196 KB n=2000
73 Correct 36 ms 43268 KB n=2000
74 Correct 42 ms 43184 KB n=1844
75 Correct 38 ms 43344 KB n=2000
76 Correct 40 ms 43200 KB n=2000
77 Correct 38 ms 43312 KB n=2000
78 Correct 36 ms 43216 KB n=2000
79 Correct 37 ms 43244 KB n=2000
80 Correct 38 ms 43276 KB n=2000
81 Correct 37 ms 43312 KB n=2000
82 Correct 37 ms 43300 KB n=2000
83 Correct 40 ms 43316 KB n=2000
84 Correct 39 ms 43212 KB n=2000
85 Correct 45 ms 43324 KB n=2000
86 Correct 40 ms 43236 KB n=2000
87 Correct 37 ms 43216 KB n=2000
88 Correct 40 ms 43380 KB n=2000
89 Correct 37 ms 43352 KB n=2000
90 Correct 39 ms 43372 KB n=2000
91 Correct 47 ms 43300 KB n=2000
92 Correct 844 ms 114592 KB n=200000
93 Correct 1317 ms 119488 KB n=200000
94 Correct 1218 ms 122444 KB n=200000
95 Correct 849 ms 114272 KB n=200000
96 Correct 797 ms 114412 KB n=200000
97 Correct 1314 ms 118672 KB n=200000
98 Correct 840 ms 114336 KB n=200000
99 Correct 1010 ms 114720 KB n=200000
100 Correct 828 ms 114300 KB n=200000
101 Correct 1198 ms 123236 KB n=200000
102 Correct 523 ms 115612 KB n=200000
103 Correct 509 ms 115588 KB n=200000
104 Correct 501 ms 115668 KB n=200000
105 Correct 527 ms 116240 KB n=200000
106 Correct 520 ms 116060 KB n=200000
107 Correct 495 ms 116028 KB n=200000
108 Correct 935 ms 114692 KB n=200000
109 Correct 929 ms 114572 KB n=200000
110 Correct 928 ms 114620 KB n=200000
111 Correct 786 ms 113672 KB n=200000
112 Correct 1196 ms 122668 KB n=200000
113 Correct 1288 ms 118432 KB n=200000
114 Correct 847 ms 113788 KB n=200000
115 Correct 1307 ms 116432 KB n=200000
116 Correct 822 ms 114504 KB n=200000
117 Correct 1206 ms 122668 KB n=200000
118 Correct 1293 ms 117324 KB n=200000
119 Correct 775 ms 114360 KB n=200000
120 Correct 1117 ms 122192 KB n=200000
121 Correct 1112 ms 122192 KB n=200000
122 Correct 1118 ms 122516 KB n=200000
123 Correct 536 ms 115916 KB n=200000
124 Correct 298 ms 60364 KB n=25264