oj.uz

Submission #628796

# Submission time Handle Problem Language Result Execution time Memory
628796 2022-08-13T17:13:03 Z BackNoob Birthday gift (IZhO18_treearray) C++14
100 / 100
 1394 ms 124040 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
int n;
int m;
int q;
int a[mxN];
int depth[mxN];
int par[mxN][LOG + 2];
vector<int> adj[mxN];
multiset<int> pos[mxN];
multiset<int> lca[mxN];
 
void dfs(int u, int p)
{
	for(int v : adj[u]) {
		if(v == p) continue;
		par[v][0] = u;
		depth[v] = depth[u] + 1;
		dfs(v, u);
	}
}

int getlca(int u, int v)
{
	if(depth[u] < depth[v]) swap(u, v);

	for(int j = LOG; j >= 0; j--) 
		if(depth[par[u][j]] >= depth[v]) u = par[u][j];

	if(u == v) return u;

	for(int j = LOG; j >= 0; j--) {
		if(par[u][j] != par[v][j]) {
			u = par[u][j];
			v = par[v][j];
		}
	}
	return par[u][0];
}
void solve()
{
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	par[1][0] = 1;
	dfs(1, -1);


	for(int j = 1; j <= LOG; j++)
	for(int i = 1; i <= n; i++) par[i][j] = par[par[i][j - 1]][j - 1];


	for(int i = 1; i <= m; i++) {
		cin >> a[i];
		pos[a[i]].insert(i);
	}

	for(int i = 1; i < m; i++) {
		lca[getlca(a[i], a[i + 1])].insert(i);
	}


	while(q--) {
		int op;
		cin >> op;
		if(op == 1) {
			int p, val;
			cin >> p >> val;

			pos[a[p]].erase(pos[a[p]].find(p));
			if(p > 1) {
				int _lca = getlca(a[p], a[p - 1]);
				lca[_lca].erase(lca[_lca].find(p - 1));
			}
			if(p < m) {
				int _lca = getlca(a[p], a[p + 1]);
				lca[_lca].erase(lca[_lca].find(p));
			}
			a[p] = val;
			pos[a[p]].insert(p);

			if(p < m) {
				int _lca = getlca(a[p], a[p + 1]);
				lca[_lca].insert(p);
			}
			if(p > 1) {
				int _lca = getlca(a[p], a[p - 1]);
				lca[_lca].insert(p - 1);
			}
		}
		else {
			int l, r, x;
			cin >> l >> r >> x;

			auto it = pos[x].lower_bound(l);
			if(it != pos[x].end()) {
				int tmp = *it;
				if(tmp <= r) {
					cout << tmp << ' ' << tmp << endl;
					continue;
				}
			}

			it = lca[x].lower_bound(l);
			if(it != lca[x].end()) {
				int tmp = *it;
				if(tmp + 1 <= r) {
					cout << tmp << ' ' << tmp + 1 << endl;
					continue;
				}
			}
			cout << -1 << ' ' << -1 << endl;

		}
	}


}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

 
    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58964 KB n=5
2 Correct 28 ms 59064 KB n=100
3 Correct 28 ms 59008 KB n=100
4 Correct 32 ms 58992 KB n=100
5 Correct 32 ms 58964 KB n=100
6 Correct 37 ms 58964 KB n=100
7 Correct 29 ms 58968 KB n=100
8 Correct 30 ms 59088 KB n=100
9 Correct 28 ms 59092 KB n=100
10 Correct 30 ms 59072 KB n=100
11 Correct 28 ms 58992 KB n=100
12 Correct 29 ms 59008 KB n=100
13 Correct 29 ms 58992 KB n=100
14 Correct 29 ms 59092 KB n=100
15 Correct 30 ms 59108 KB n=100
16 Correct 31 ms 59028 KB n=100
17 Correct 30 ms 59104 KB n=100
18 Correct 29 ms 59008 KB n=100
19 Correct 33 ms 59092 KB n=100
20 Correct 31 ms 59104 KB n=100
21 Correct 44 ms 59036 KB n=100
22 Correct 30 ms 59092 KB n=100
23 Correct 28 ms 59068 KB n=100
24 Correct 29 ms 59040 KB n=100
25 Correct 33 ms 59084 KB n=100
26 Correct 29 ms 58956 KB n=12
27 Correct 31 ms 59072 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58964 KB n=5
2 Correct 28 ms 59064 KB n=100
3 Correct 28 ms 59008 KB n=100
4 Correct 32 ms 58992 KB n=100
5 Correct 32 ms 58964 KB n=100
6 Correct 37 ms 58964 KB n=100
7 Correct 29 ms 58968 KB n=100
8 Correct 30 ms 59088 KB n=100
9 Correct 28 ms 59092 KB n=100
10 Correct 30 ms 59072 KB n=100
11 Correct 28 ms 58992 KB n=100
12 Correct 29 ms 59008 KB n=100
13 Correct 29 ms 58992 KB n=100
14 Correct 29 ms 59092 KB n=100
15 Correct 30 ms 59108 KB n=100
16 Correct 31 ms 59028 KB n=100
17 Correct 30 ms 59104 KB n=100
18 Correct 29 ms 59008 KB n=100
19 Correct 33 ms 59092 KB n=100
20 Correct 31 ms 59104 KB n=100
21 Correct 44 ms 59036 KB n=100
22 Correct 30 ms 59092 KB n=100
23 Correct 28 ms 59068 KB n=100
24 Correct 29 ms 59040 KB n=100
25 Correct 33 ms 59084 KB n=100
26 Correct 29 ms 58956 KB n=12
27 Correct 31 ms 59072 KB n=100
28 Correct 36 ms 59196 KB n=500
29 Correct 36 ms 59196 KB n=500
30 Correct 33 ms 59080 KB n=500
31 Correct 31 ms 59260 KB n=500
32 Correct 31 ms 59200 KB n=500
33 Correct 31 ms 59092 KB n=500
34 Correct 35 ms 59184 KB n=500
35 Correct 31 ms 59176 KB n=500
36 Correct 30 ms 59092 KB n=500
37 Correct 32 ms 59092 KB n=500
38 Correct 30 ms 59092 KB n=500
39 Correct 37 ms 59084 KB n=500
40 Correct 29 ms 59068 KB n=500
41 Correct 29 ms 59204 KB n=500
42 Correct 29 ms 59100 KB n=500
43 Correct 29 ms 59108 KB n=500
44 Correct 29 ms 59184 KB n=500
45 Correct 30 ms 59192 KB n=500
46 Correct 31 ms 59220 KB n=500
47 Correct 29 ms 59240 KB n=500
48 Correct 29 ms 59128 KB n=500
49 Correct 29 ms 59136 KB n=500
50 Correct 30 ms 59084 KB n=500
51 Correct 37 ms 59124 KB n=500
52 Correct 38 ms 59192 KB n=500
53 Correct 30 ms 59148 KB n=500
54 Correct 29 ms 59220 KB n=500
55 Correct 29 ms 59072 KB n=278
56 Correct 31 ms 59136 KB n=500
57 Correct 36 ms 59204 KB n=500
58 Correct 32 ms 59092 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58964 KB n=5
2 Correct 28 ms 59064 KB n=100
3 Correct 28 ms 59008 KB n=100
4 Correct 32 ms 58992 KB n=100
5 Correct 32 ms 58964 KB n=100
6 Correct 37 ms 58964 KB n=100
7 Correct 29 ms 58968 KB n=100
8 Correct 30 ms 59088 KB n=100
9 Correct 28 ms 59092 KB n=100
10 Correct 30 ms 59072 KB n=100
11 Correct 28 ms 58992 KB n=100
12 Correct 29 ms 59008 KB n=100
13 Correct 29 ms 58992 KB n=100
14 Correct 29 ms 59092 KB n=100
15 Correct 30 ms 59108 KB n=100
16 Correct 31 ms 59028 KB n=100
17 Correct 30 ms 59104 KB n=100
18 Correct 29 ms 59008 KB n=100
19 Correct 33 ms 59092 KB n=100
20 Correct 31 ms 59104 KB n=100
21 Correct 44 ms 59036 KB n=100
22 Correct 30 ms 59092 KB n=100
23 Correct 28 ms 59068 KB n=100
24 Correct 29 ms 59040 KB n=100
25 Correct 33 ms 59084 KB n=100
26 Correct 29 ms 58956 KB n=12
27 Correct 31 ms 59072 KB n=100
28 Correct 36 ms 59196 KB n=500
29 Correct 36 ms 59196 KB n=500
30 Correct 33 ms 59080 KB n=500
31 Correct 31 ms 59260 KB n=500
32 Correct 31 ms 59200 KB n=500
33 Correct 31 ms 59092 KB n=500
34 Correct 35 ms 59184 KB n=500
35 Correct 31 ms 59176 KB n=500
36 Correct 30 ms 59092 KB n=500
37 Correct 32 ms 59092 KB n=500
38 Correct 30 ms 59092 KB n=500
39 Correct 37 ms 59084 KB n=500
40 Correct 29 ms 59068 KB n=500
41 Correct 29 ms 59204 KB n=500
42 Correct 29 ms 59100 KB n=500
43 Correct 29 ms 59108 KB n=500
44 Correct 29 ms 59184 KB n=500
45 Correct 30 ms 59192 KB n=500
46 Correct 31 ms 59220 KB n=500
47 Correct 29 ms 59240 KB n=500
48 Correct 29 ms 59128 KB n=500
49 Correct 29 ms 59136 KB n=500
50 Correct 30 ms 59084 KB n=500
51 Correct 37 ms 59124 KB n=500
52 Correct 38 ms 59192 KB n=500
53 Correct 30 ms 59148 KB n=500
54 Correct 29 ms 59220 KB n=500
55 Correct 29 ms 59072 KB n=278
56 Correct 31 ms 59136 KB n=500
57 Correct 36 ms 59204 KB n=500
58 Correct 32 ms 59092 KB n=500
59 Correct 34 ms 59460 KB n=2000
60 Correct 34 ms 59596 KB n=2000
61 Correct 33 ms 59596 KB n=2000
62 Correct 31 ms 59504 KB n=2000
63 Correct 37 ms 59564 KB n=2000
64 Correct 32 ms 59504 KB n=2000
65 Correct 35 ms 59464 KB n=2000
66 Correct 36 ms 59596 KB n=2000
67 Correct 34 ms 59540 KB n=2000
68 Correct 32 ms 59596 KB n=2000
69 Correct 39 ms 59568 KB n=2000
70 Correct 38 ms 59568 KB n=2000
71 Correct 32 ms 59568 KB n=2000
72 Correct 35 ms 59476 KB n=2000
73 Correct 32 ms 59500 KB n=2000
74 Correct 35 ms 59476 KB n=1844
75 Correct 32 ms 59460 KB n=2000
76 Correct 33 ms 59476 KB n=2000
77 Correct 36 ms 59448 KB n=2000
78 Correct 37 ms 59456 KB n=2000
79 Correct 33 ms 59492 KB n=2000
80 Correct 39 ms 59592 KB n=2000
81 Correct 32 ms 59604 KB n=2000
82 Correct 32 ms 59552 KB n=2000
83 Correct 38 ms 59572 KB n=2000
84 Correct 32 ms 59548 KB n=2000
85 Correct 34 ms 59628 KB n=2000
86 Correct 36 ms 59516 KB n=2000
87 Correct 33 ms 59560 KB n=2000
88 Correct 32 ms 59656 KB n=2000
89 Correct 32 ms 59676 KB n=2000
90 Correct 35 ms 59620 KB n=2000
91 Correct 31 ms 59468 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58964 KB n=5
2 Correct 28 ms 59064 KB n=100
3 Correct 28 ms 59008 KB n=100
4 Correct 32 ms 58992 KB n=100
5 Correct 32 ms 58964 KB n=100
6 Correct 37 ms 58964 KB n=100
7 Correct 29 ms 58968 KB n=100
8 Correct 30 ms 59088 KB n=100
9 Correct 28 ms 59092 KB n=100
10 Correct 30 ms 59072 KB n=100
11 Correct 28 ms 58992 KB n=100
12 Correct 29 ms 59008 KB n=100
13 Correct 29 ms 58992 KB n=100
14 Correct 29 ms 59092 KB n=100
15 Correct 30 ms 59108 KB n=100
16 Correct 31 ms 59028 KB n=100
17 Correct 30 ms 59104 KB n=100
18 Correct 29 ms 59008 KB n=100
19 Correct 33 ms 59092 KB n=100
20 Correct 31 ms 59104 KB n=100
21 Correct 44 ms 59036 KB n=100
22 Correct 30 ms 59092 KB n=100
23 Correct 28 ms 59068 KB n=100
24 Correct 29 ms 59040 KB n=100
25 Correct 33 ms 59084 KB n=100
26 Correct 29 ms 58956 KB n=12
27 Correct 31 ms 59072 KB n=100
28 Correct 36 ms 59196 KB n=500
29 Correct 36 ms 59196 KB n=500
30 Correct 33 ms 59080 KB n=500
31 Correct 31 ms 59260 KB n=500
32 Correct 31 ms 59200 KB n=500
33 Correct 31 ms 59092 KB n=500
34 Correct 35 ms 59184 KB n=500
35 Correct 31 ms 59176 KB n=500
36 Correct 30 ms 59092 KB n=500
37 Correct 32 ms 59092 KB n=500
38 Correct 30 ms 59092 KB n=500
39 Correct 37 ms 59084 KB n=500
40 Correct 29 ms 59068 KB n=500
41 Correct 29 ms 59204 KB n=500
42 Correct 29 ms 59100 KB n=500
43 Correct 29 ms 59108 KB n=500
44 Correct 29 ms 59184 KB n=500
45 Correct 30 ms 59192 KB n=500
46 Correct 31 ms 59220 KB n=500
47 Correct 29 ms 59240 KB n=500
48 Correct 29 ms 59128 KB n=500
49 Correct 29 ms 59136 KB n=500
50 Correct 30 ms 59084 KB n=500
51 Correct 37 ms 59124 KB n=500
52 Correct 38 ms 59192 KB n=500
53 Correct 30 ms 59148 KB n=500
54 Correct 29 ms 59220 KB n=500
55 Correct 29 ms 59072 KB n=278
56 Correct 31 ms 59136 KB n=500
57 Correct 36 ms 59204 KB n=500
58 Correct 32 ms 59092 KB n=500
59 Correct 34 ms 59460 KB n=2000
60 Correct 34 ms 59596 KB n=2000
61 Correct 33 ms 59596 KB n=2000
62 Correct 31 ms 59504 KB n=2000
63 Correct 37 ms 59564 KB n=2000
64 Correct 32 ms 59504 KB n=2000
65 Correct 35 ms 59464 KB n=2000
66 Correct 36 ms 59596 KB n=2000
67 Correct 34 ms 59540 KB n=2000
68 Correct 32 ms 59596 KB n=2000
69 Correct 39 ms 59568 KB n=2000
70 Correct 38 ms 59568 KB n=2000
71 Correct 32 ms 59568 KB n=2000
72 Correct 35 ms 59476 KB n=2000
73 Correct 32 ms 59500 KB n=2000
74 Correct 35 ms 59476 KB n=1844
75 Correct 32 ms 59460 KB n=2000
76 Correct 33 ms 59476 KB n=2000
77 Correct 36 ms 59448 KB n=2000
78 Correct 37 ms 59456 KB n=2000
79 Correct 33 ms 59492 KB n=2000
80 Correct 39 ms 59592 KB n=2000
81 Correct 32 ms 59604 KB n=2000
82 Correct 32 ms 59552 KB n=2000
83 Correct 38 ms 59572 KB n=2000
84 Correct 32 ms 59548 KB n=2000
85 Correct 34 ms 59628 KB n=2000
86 Correct 36 ms 59516 KB n=2000
87 Correct 33 ms 59560 KB n=2000
88 Correct 32 ms 59656 KB n=2000
89 Correct 32 ms 59676 KB n=2000
90 Correct 35 ms 59620 KB n=2000
91 Correct 31 ms 59468 KB n=2000
92 Correct 759 ms 111492 KB n=200000
93 Correct 1201 ms 117764 KB n=200000
94 Correct 1161 ms 122192 KB n=200000
95 Correct 777 ms 111152 KB n=200000
96 Correct 793 ms 111240 KB n=200000
97 Correct 1268 ms 116652 KB n=200000
98 Correct 799 ms 111252 KB n=200000
99 Correct 932 ms 111348 KB n=200000
100 Correct 768 ms 111356 KB n=200000
101 Correct 1121 ms 124040 KB n=200000
102 Correct 446 ms 112372 KB n=200000
103 Correct 432 ms 112352 KB n=200000
104 Correct 430 ms 112324 KB n=200000
105 Correct 473 ms 112792 KB n=200000
106 Correct 457 ms 112860 KB n=200000
107 Correct 445 ms 112760 KB n=200000
108 Correct 924 ms 111300 KB n=200000
109 Correct 918 ms 111292 KB n=200000
110 Correct 882 ms 111328 KB n=200000
111 Correct 715 ms 110640 KB n=200000
112 Correct 1122 ms 122668 KB n=200000
113 Correct 1269 ms 116748 KB n=200000
114 Correct 844 ms 110632 KB n=200000
115 Correct 1394 ms 113780 KB n=200000
116 Correct 811 ms 111320 KB n=200000
117 Correct 1321 ms 123096 KB n=200000
118 Correct 1349 ms 115056 KB n=200000
119 Correct 857 ms 111352 KB n=200000
120 Correct 1191 ms 122976 KB n=200000
121 Correct 1284 ms 122996 KB n=200000
122 Correct 1261 ms 123288 KB n=200000
123 Correct 519 ms 112560 KB n=200000
124 Correct 304 ms 74508 KB n=25264