oj.uz

Submission #379662

# Submission time Handle Problem Language Result Execution time Memory
379662 2021-03-19T02:05:17 Z Kevin_Zhang_TW Birthday gift (IZhO18_treearray) C++17
100 / 100
 2334 ms 107092 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010, MAX_K = 18;

int n, m, q;
vector<int> edge[MAX_N];

int a[MAX_N];

set<int> two[MAX_N], one[MAX_N];

int anc[MAX_K][MAX_N], in[MAX_N], out[MAX_N];

bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }

void dfs(int x, int lst) {
	static int t;
	in[x] = t++;
	anc[0][x] = lst;
	for (int u : edge[x]) if (u != lst)
		dfs(u, x);
	out[x] = t;
}

void initlca() {
	dfs(1, 1);
	for (int d = 1;d < MAX_K;++d)
		for (int i = 1;i <= n;++i)
			anc[d][i] = anc[d-1][anc[d-1][i]];
}

bool inr(int ind) { return ind >= 1 && ind <= n; }

int lca(int a, int b) {
	for (int d = MAX_K - 1;d >= 0;--d)
		if (!isanc(anc[d][a], b)) a = anc[d][a];
	return isanc(a, b) ? a : anc[0][a];
}

void chg(int ind, int d) {
	if (ind == 0) return;
	int la = lca(a[ind], a[ind+1]), lb = a[ind];
	if (d == 1) {
		two[la].insert(ind);
		one[lb].insert(ind);
	}
	else {
		two[la].erase(ind);
		one[lb].erase(ind);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> q;
	for (int a, b, i = 1;i < n;++i) {
		cin >> a >> b;
		edge[a].pb(b), edge[b].pb(a);
	}
	for (int i = 1;i <= m;++i)
		cin >> a[i];

	a[m+1] = 1;

	initlca();

	for (int i = 1;i <= m;++i)
		chg(i, 1);

	for (int i = 1;i <= m;++i)
		two[i].insert(m+1), one[i].insert(m+1);

	for (int t, l, r, v, pos, i = 0;i < q;++i) {
		cin >> t;
		if (t == 1) {
			cin >> pos >> v;
			chg(pos-1, -1), chg(pos, -1);
			
			a[pos] = v;

			chg(pos-1, 1), chg(pos, 1);
		}
		if (t == 2) {
			cin >> l >> r >> v;
			int p = *two[v].lower_bound(l);
			int q = *one[v].lower_bound(l);
			if (q <= r) {
				cout << q << ' ' << q << '\n';
			}
			else if (p < r)
				cout << p << ' ' << p+1 << '\n';
			else
				cout << "-1 -1\n";
		}
	}

}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35692 KB n=5
2 Correct 24 ms 35692 KB n=100
3 Correct 26 ms 35692 KB n=100
4 Correct 27 ms 35692 KB n=100
5 Correct 25 ms 35692 KB n=100
6 Correct 28 ms 35692 KB n=100
7 Correct 26 ms 35692 KB n=100
8 Correct 24 ms 35692 KB n=100
9 Correct 24 ms 35692 KB n=100
10 Correct 24 ms 35692 KB n=100
11 Correct 27 ms 35692 KB n=100
12 Correct 24 ms 35692 KB n=100
13 Correct 25 ms 35692 KB n=100
14 Correct 24 ms 35692 KB n=100
15 Correct 24 ms 35692 KB n=100
16 Correct 26 ms 35724 KB n=100
17 Correct 25 ms 35692 KB n=100
18 Correct 24 ms 35692 KB n=100
19 Correct 28 ms 35692 KB n=100
20 Correct 24 ms 35692 KB n=100
21 Correct 26 ms 35692 KB n=100
22 Correct 24 ms 35692 KB n=100
23 Correct 27 ms 35692 KB n=100
24 Correct 26 ms 35692 KB n=100
25 Correct 27 ms 35712 KB n=100
26 Correct 26 ms 35692 KB n=12
27 Correct 25 ms 35692 KB n=100

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35692 KB n=5
2 Correct 24 ms 35692 KB n=100
3 Correct 26 ms 35692 KB n=100
4 Correct 27 ms 35692 KB n=100
5 Correct 25 ms 35692 KB n=100
6 Correct 28 ms 35692 KB n=100
7 Correct 26 ms 35692 KB n=100
8 Correct 24 ms 35692 KB n=100
9 Correct 24 ms 35692 KB n=100
10 Correct 24 ms 35692 KB n=100
11 Correct 27 ms 35692 KB n=100
12 Correct 24 ms 35692 KB n=100
13 Correct 25 ms 35692 KB n=100
14 Correct 24 ms 35692 KB n=100
15 Correct 24 ms 35692 KB n=100
16 Correct 26 ms 35724 KB n=100
17 Correct 25 ms 35692 KB n=100
18 Correct 24 ms 35692 KB n=100
19 Correct 28 ms 35692 KB n=100
20 Correct 24 ms 35692 KB n=100
21 Correct 26 ms 35692 KB n=100
22 Correct 24 ms 35692 KB n=100
23 Correct 27 ms 35692 KB n=100
24 Correct 26 ms 35692 KB n=100
25 Correct 27 ms 35712 KB n=100
26 Correct 26 ms 35692 KB n=12
27 Correct 25 ms 35692 KB n=100
28 Correct 27 ms 35820 KB n=500
29 Correct 28 ms 35820 KB n=500
30 Correct 25 ms 35820 KB n=500
31 Correct 26 ms 35820 KB n=500
32 Correct 27 ms 35820 KB n=500
33 Correct 28 ms 35820 KB n=500
34 Correct 24 ms 35820 KB n=500
35 Correct 25 ms 35820 KB n=500
36 Correct 25 ms 35820 KB n=500
37 Correct 29 ms 35820 KB n=500
38 Correct 25 ms 35820 KB n=500
39 Correct 30 ms 35820 KB n=500
40 Correct 24 ms 35820 KB n=500
41 Correct 25 ms 35820 KB n=500
42 Correct 25 ms 35820 KB n=500
43 Correct 26 ms 35820 KB n=500
44 Correct 27 ms 35820 KB n=500
45 Correct 27 ms 36076 KB n=500
46 Correct 25 ms 35820 KB n=500
47 Correct 25 ms 35820 KB n=500
48 Correct 25 ms 35820 KB n=500
49 Correct 25 ms 35820 KB n=500
50 Correct 25 ms 35820 KB n=500
51 Correct 26 ms 35820 KB n=500
52 Correct 27 ms 35820 KB n=500
53 Correct 27 ms 35820 KB n=500
54 Correct 28 ms 35820 KB n=500
55 Correct 24 ms 35820 KB n=278
56 Correct 25 ms 35820 KB n=500
57 Correct 28 ms 35820 KB n=500
58 Correct 24 ms 35820 KB n=500
59 Correct 28 ms 36332 KB n=2000
60 Correct 28 ms 36460 KB n=2000
61 Correct 28 ms 36460 KB n=2000
62 Correct 30 ms 36332 KB n=2000
63 Correct 33 ms 36332 KB n=2000
64 Correct 29 ms 36332 KB n=2000
65 Correct 29 ms 36332 KB n=2000
66 Correct 28 ms 36460 KB n=2000
67 Correct 31 ms 36460 KB n=2000
68 Correct 28 ms 36460 KB n=2000
69 Correct 27 ms 36332 KB n=2000
70 Correct 28 ms 36332 KB n=2000
71 Correct 31 ms 36332 KB n=2000
72 Correct 26 ms 36332 KB n=2000
73 Correct 30 ms 36332 KB n=2000
74 Correct 28 ms 36332 KB n=1844
75 Correct 29 ms 36332 KB n=2000
76 Correct 33 ms 36332 KB n=2000
77 Correct 30 ms 36332 KB n=2000
78 Correct 32 ms 36332 KB n=2000
79 Correct 29 ms 36332 KB n=2000
80 Correct 28 ms 36460 KB n=2000
81 Correct 28 ms 36332 KB n=2000
82 Correct 29 ms 36332 KB n=2000
83 Correct 28 ms 36460 KB n=2000
84 Correct 28 ms 36332 KB n=2000
85 Correct 29 ms 36332 KB n=2000
86 Correct 28 ms 36332 KB n=2000
87 Correct 29 ms 36332 KB n=2000
88 Correct 29 ms 36460 KB n=2000
89 Correct 31 ms 36460 KB n=2000
90 Correct 28 ms 36460 KB n=2000
91 Correct 30 ms 36332 KB n=2000
92 Correct 1976 ms 98484 KB n=200000
93 Correct 2159 ms 102300 KB n=200000
94 Correct 2117 ms 105804 KB n=200000
95 Correct 1967 ms 98408 KB n=200000
96 Correct 1975 ms 98308 KB n=200000
97 Correct 2151 ms 101340 KB n=200000
98 Correct 1980 ms 98400 KB n=200000
99 Correct 1972 ms 97988 KB n=200000
100 Correct 1968 ms 98512 KB n=200000
101 Correct 2009 ms 107092 KB n=200000
102 Correct 827 ms 99436 KB n=200000
103 Correct 860 ms 99308 KB n=200000
104 Correct 833 ms 99564 KB n=200000
105 Correct 827 ms 99180 KB n=200000
106 Correct 860 ms 99156 KB n=200000
107 Correct 831 ms 99180 KB n=200000
108 Correct 1796 ms 98112 KB n=200000
109 Correct 1767 ms 98180 KB n=200000
110 Correct 1812 ms 98108 KB n=200000
111 Correct 1807 ms 98448 KB n=200000
112 Correct 2074 ms 106104 KB n=200000
113 Correct 2124 ms 101360 KB n=200000
114 Correct 1815 ms 98528 KB n=200000
115 Correct 2334 ms 99324 KB n=200000
116 Correct 1927 ms 98264 KB n=200000
117 Correct 1990 ms 106296 KB n=200000
118 Correct 2133 ms 100444 KB n=200000
119 Correct 1847 ms 98316 KB n=200000
120 Correct 1907 ms 106732 KB n=200000
121 Correct 1947 ms 106780 KB n=200000
122 Correct 2047 ms 106988 KB n=200000
123 Correct 891 ms 98784 KB n=200000
124 Correct 382 ms 57580 KB n=25264