oj.uz

Submission #41562

# Submission time Handle Problem Language Result Execution time Memory
41562 2018-02-19T01:47:35 Z aome Birthday gift (IZhO18_treearray) C++14
56 / 100
 4000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

typedef pair<int, int> ii;

struct SegmentTree {
	int a[N];
	set<ii> it[4 * N];

	void build(int i, int l, int r) {
		for (int j = l; j <= r; ++j) it[i].insert(ii(a[j], j));
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	} 

	void init(int n, int a[]) {
		for (int i = 1; i <= n; ++i) this -> a[i] = a[i];
		build(1, 1, n);
	}

	void upd(int i, int l, int r, ii x, bool type) {
		if (type == 0) it[i].insert(x);
		if (type == 1) it[i].erase(x);
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (mid >= x.second) upd(i << 1, l, mid, x, type);
		else upd(i << 1 | 1, mid + 1, r, x, type);
	}

	int find(int i, int l, int r, int L, int R, int x) {
		if (l > R || L > r) return 0;
		if (L <= l && r <= R) {
			auto j = it[i].lower_bound(ii(x, 0));
			if (j != it[i].end() && j -> first == x) return j -> second;
			return 0;
		}
		int mid = (l + r) >> 1;
		return max(find(i << 1, l, mid, L, R, x), find(i << 1 | 1, mid + 1, r, L, R, x));
	}

} IT1, IT2;

int n, m, q;
int a[N];
int b[N];
int high[N];
int p[20][N];
vector<int> G[N];

int lca(int u, int v) {
	if (high[u] > high[v]) swap(u, v);
	for (int i = 18; i >= 0; --i) {
		if (high[p[i][v]] >= high[u]) v = p[i][v];
	}
	for (int i = 18; i >= 0; --i) {
		if (p[i][v] != p[i][u]) v = p[i][v], u = p[i][u];
	}
	return (u == v) ? u : p[0][u];
}

void dfs(int u) {
	for (auto v : G[u]) {
		if (p[0][u] == v) continue;
		p[0][v] = u, high[v] = high[u] + 1, dfs(v);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
	}
	p[0][1] = 1, dfs(1);
	for (int i = 1; i <= 18; ++i) {
		for (int j = 1; j <= n; ++j) {
			p[i][j] = p[i - 1][p[i - 1][j]];
		}
	}
	for (int i = 1; i <= m; ++i) cin >> a[i];
	IT1.init(m, a);
	for (int i = 1; i < m; ++i) b[i] = lca(a[i], a[i + 1]);
	IT2.init(m - 1, b);
	while (q--) {
		int type; cin >> type;
		if (type == 1) {
			int pos, v; cin >> pos >> v;
			IT1.upd(1, 1, m, ii(a[pos], pos), 1);
			IT1.upd(1, 1, m, ii(v, pos), 0);
			if (pos > 1) {
				IT2.upd(1, 1, m - 1, ii(lca(a[pos - 1], a[pos]), pos - 1), 1);
				IT2.upd(1, 1, m - 1, ii(lca(a[pos - 1], v), pos - 1), 0);
			}
			if (pos < m) {
				IT2.upd(1, 1, m - 1, ii(lca(a[pos], a[pos + 1]), pos), 1);
				IT2.upd(1, 1, m - 1, ii(lca(v, a[pos + 1]), pos), 0);
			}
			a[pos] = v;
		}
		else {
			int l, r, v; cin >> l >> r >> v;
			int res = 0;
			res = IT1.find(1, 1, m, l, r, v);
			if (!res) {
				res = IT2.find(1, 1, m - 1, l, r - 1, v);
				if (res) {
					cout << res << ' ' << res + 1 << '\n'; continue;
				}
			}
			else {
				cout << res << ' ' << res << '\n'; continue;
			}
			cout << "-1 -1\n";
		}
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 80248 KB n=5
2 Correct 67 ms 80480 KB n=100
3 Correct 66 ms 80480 KB n=100
4 Correct 65 ms 80592 KB n=100
5 Correct 65 ms 80592 KB n=100
6 Correct 66 ms 80612 KB n=100
7 Correct 70 ms 80684 KB n=100
8 Correct 64 ms 80684 KB n=100
9 Correct 65 ms 80684 KB n=100
10 Correct 69 ms 80684 KB n=100
11 Correct 70 ms 80684 KB n=100
12 Correct 66 ms 80684 KB n=100
13 Correct 75 ms 80684 KB n=100
14 Correct 66 ms 80684 KB n=100
15 Correct 68 ms 80684 KB n=100
16 Correct 68 ms 80684 KB n=100
17 Correct 66 ms 80684 KB n=100
18 Correct 70 ms 80732 KB n=100
19 Correct 68 ms 80732 KB n=100
20 Correct 71 ms 80732 KB n=100
21 Correct 66 ms 80732 KB n=100
22 Correct 69 ms 80732 KB n=100
23 Correct 70 ms 80996 KB n=100
24 Correct 66 ms 80996 KB n=100
25 Correct 68 ms 80996 KB n=100
26 Correct 74 ms 80996 KB n=12
27 Correct 69 ms 80996 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 80248 KB n=5
2 Correct 67 ms 80480 KB n=100
3 Correct 66 ms 80480 KB n=100
4 Correct 65 ms 80592 KB n=100
5 Correct 65 ms 80592 KB n=100
6 Correct 66 ms 80612 KB n=100
7 Correct 70 ms 80684 KB n=100
8 Correct 64 ms 80684 KB n=100
9 Correct 65 ms 80684 KB n=100
10 Correct 69 ms 80684 KB n=100
11 Correct 70 ms 80684 KB n=100
12 Correct 66 ms 80684 KB n=100
13 Correct 75 ms 80684 KB n=100
14 Correct 66 ms 80684 KB n=100
15 Correct 68 ms 80684 KB n=100
16 Correct 68 ms 80684 KB n=100
17 Correct 66 ms 80684 KB n=100
18 Correct 70 ms 80732 KB n=100
19 Correct 68 ms 80732 KB n=100
20 Correct 71 ms 80732 KB n=100
21 Correct 66 ms 80732 KB n=100
22 Correct 69 ms 80732 KB n=100
23 Correct 70 ms 80996 KB n=100
24 Correct 66 ms 80996 KB n=100
25 Correct 68 ms 80996 KB n=100
26 Correct 74 ms 80996 KB n=12
27 Correct 69 ms 80996 KB n=100
28 Correct 74 ms 81144 KB n=500
29 Correct 74 ms 81144 KB n=500
30 Correct 70 ms 81172 KB n=500
31 Correct 70 ms 81188 KB n=500
32 Correct 70 ms 81296 KB n=500
33 Correct 72 ms 81296 KB n=500
34 Correct 70 ms 81296 KB n=500
35 Correct 71 ms 81296 KB n=500
36 Correct 68 ms 81296 KB n=500
37 Correct 70 ms 81296 KB n=500
38 Correct 70 ms 81296 KB n=500
39 Correct 75 ms 81424 KB n=500
40 Correct 68 ms 81424 KB n=500
41 Correct 68 ms 81424 KB n=500
42 Correct 72 ms 81424 KB n=500
43 Correct 71 ms 81424 KB n=500
44 Correct 71 ms 81476 KB n=500
45 Correct 75 ms 81476 KB n=500
46 Correct 70 ms 81476 KB n=500
47 Correct 71 ms 81476 KB n=500
48 Correct 72 ms 81516 KB n=500
49 Correct 82 ms 81516 KB n=500
50 Correct 73 ms 81532 KB n=500
51 Correct 71 ms 81532 KB n=500
52 Correct 86 ms 81532 KB n=500
53 Correct 70 ms 81532 KB n=500
54 Correct 69 ms 81532 KB n=500
55 Correct 75 ms 81532 KB n=278
56 Correct 74 ms 81532 KB n=500
57 Correct 71 ms 81544 KB n=500
58 Correct 72 ms 81556 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 80248 KB n=5
2 Correct 67 ms 80480 KB n=100
3 Correct 66 ms 80480 KB n=100
4 Correct 65 ms 80592 KB n=100
5 Correct 65 ms 80592 KB n=100
6 Correct 66 ms 80612 KB n=100
7 Correct 70 ms 80684 KB n=100
8 Correct 64 ms 80684 KB n=100
9 Correct 65 ms 80684 KB n=100
10 Correct 69 ms 80684 KB n=100
11 Correct 70 ms 80684 KB n=100
12 Correct 66 ms 80684 KB n=100
13 Correct 75 ms 80684 KB n=100
14 Correct 66 ms 80684 KB n=100
15 Correct 68 ms 80684 KB n=100
16 Correct 68 ms 80684 KB n=100
17 Correct 66 ms 80684 KB n=100
18 Correct 70 ms 80732 KB n=100
19 Correct 68 ms 80732 KB n=100
20 Correct 71 ms 80732 KB n=100
21 Correct 66 ms 80732 KB n=100
22 Correct 69 ms 80732 KB n=100
23 Correct 70 ms 80996 KB n=100
24 Correct 66 ms 80996 KB n=100
25 Correct 68 ms 80996 KB n=100
26 Correct 74 ms 80996 KB n=12
27 Correct 69 ms 80996 KB n=100
28 Correct 74 ms 81144 KB n=500
29 Correct 74 ms 81144 KB n=500
30 Correct 70 ms 81172 KB n=500
31 Correct 70 ms 81188 KB n=500
32 Correct 70 ms 81296 KB n=500
33 Correct 72 ms 81296 KB n=500
34 Correct 70 ms 81296 KB n=500
35 Correct 71 ms 81296 KB n=500
36 Correct 68 ms 81296 KB n=500
37 Correct 70 ms 81296 KB n=500
38 Correct 70 ms 81296 KB n=500
39 Correct 75 ms 81424 KB n=500
40 Correct 68 ms 81424 KB n=500
41 Correct 68 ms 81424 KB n=500
42 Correct 72 ms 81424 KB n=500
43 Correct 71 ms 81424 KB n=500
44 Correct 71 ms 81476 KB n=500
45 Correct 75 ms 81476 KB n=500
46 Correct 70 ms 81476 KB n=500
47 Correct 71 ms 81476 KB n=500
48 Correct 72 ms 81516 KB n=500
49 Correct 82 ms 81516 KB n=500
50 Correct 73 ms 81532 KB n=500
51 Correct 71 ms 81532 KB n=500
52 Correct 86 ms 81532 KB n=500
53 Correct 70 ms 81532 KB n=500
54 Correct 69 ms 81532 KB n=500
55 Correct 75 ms 81532 KB n=278
56 Correct 74 ms 81532 KB n=500
57 Correct 71 ms 81544 KB n=500
58 Correct 72 ms 81556 KB n=500
59 Correct 109 ms 83492 KB n=2000
60 Correct 110 ms 83676 KB n=2000
61 Correct 96 ms 83748 KB n=2000
62 Correct 97 ms 83816 KB n=2000
63 Correct 95 ms 83872 KB n=2000
64 Correct 99 ms 84068 KB n=2000
65 Correct 94 ms 84068 KB n=2000
66 Correct 94 ms 84240 KB n=2000
67 Correct 95 ms 84240 KB n=2000
68 Correct 97 ms 84240 KB n=2000
69 Correct 93 ms 84240 KB n=2000
70 Correct 81 ms 84240 KB n=2000
71 Correct 77 ms 84240 KB n=2000
72 Correct 80 ms 84260 KB n=2000
73 Correct 84 ms 84348 KB n=2000
74 Correct 93 ms 84372 KB n=1844
75 Correct 80 ms 84516 KB n=2000
76 Correct 97 ms 84516 KB n=2000
77 Correct 99 ms 84652 KB n=2000
78 Correct 102 ms 84652 KB n=2000
79 Correct 91 ms 84756 KB n=2000
80 Correct 109 ms 85000 KB n=2000
81 Correct 94 ms 85000 KB n=2000
82 Correct 95 ms 85000 KB n=2000
83 Correct 95 ms 85000 KB n=2000
84 Correct 96 ms 85000 KB n=2000
85 Correct 98 ms 85072 KB n=2000
86 Correct 95 ms 85100 KB n=2000
87 Correct 100 ms 85100 KB n=2000
88 Correct 95 ms 85252 KB n=2000
89 Correct 99 ms 85292 KB n=2000
90 Correct 96 ms 85348 KB n=2000
91 Correct 79 ms 85348 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 80248 KB n=5
2 Correct 67 ms 80480 KB n=100
3 Correct 66 ms 80480 KB n=100
4 Correct 65 ms 80592 KB n=100
5 Correct 65 ms 80592 KB n=100
6 Correct 66 ms 80612 KB n=100
7 Correct 70 ms 80684 KB n=100
8 Correct 64 ms 80684 KB n=100
9 Correct 65 ms 80684 KB n=100
10 Correct 69 ms 80684 KB n=100
11 Correct 70 ms 80684 KB n=100
12 Correct 66 ms 80684 KB n=100
13 Correct 75 ms 80684 KB n=100
14 Correct 66 ms 80684 KB n=100
15 Correct 68 ms 80684 KB n=100
16 Correct 68 ms 80684 KB n=100
17 Correct 66 ms 80684 KB n=100
18 Correct 70 ms 80732 KB n=100
19 Correct 68 ms 80732 KB n=100
20 Correct 71 ms 80732 KB n=100
21 Correct 66 ms 80732 KB n=100
22 Correct 69 ms 80732 KB n=100
23 Correct 70 ms 80996 KB n=100
24 Correct 66 ms 80996 KB n=100
25 Correct 68 ms 80996 KB n=100
26 Correct 74 ms 80996 KB n=12
27 Correct 69 ms 80996 KB n=100
28 Correct 74 ms 81144 KB n=500
29 Correct 74 ms 81144 KB n=500
30 Correct 70 ms 81172 KB n=500
31 Correct 70 ms 81188 KB n=500
32 Correct 70 ms 81296 KB n=500
33 Correct 72 ms 81296 KB n=500
34 Correct 70 ms 81296 KB n=500
35 Correct 71 ms 81296 KB n=500
36 Correct 68 ms 81296 KB n=500
37 Correct 70 ms 81296 KB n=500
38 Correct 70 ms 81296 KB n=500
39 Correct 75 ms 81424 KB n=500
40 Correct 68 ms 81424 KB n=500
41 Correct 68 ms 81424 KB n=500
42 Correct 72 ms 81424 KB n=500
43 Correct 71 ms 81424 KB n=500
44 Correct 71 ms 81476 KB n=500
45 Correct 75 ms 81476 KB n=500
46 Correct 70 ms 81476 KB n=500
47 Correct 71 ms 81476 KB n=500
48 Correct 72 ms 81516 KB n=500
49 Correct 82 ms 81516 KB n=500
50 Correct 73 ms 81532 KB n=500
51 Correct 71 ms 81532 KB n=500
52 Correct 86 ms 81532 KB n=500
53 Correct 70 ms 81532 KB n=500
54 Correct 69 ms 81532 KB n=500
55 Correct 75 ms 81532 KB n=278
56 Correct 74 ms 81532 KB n=500
57 Correct 71 ms 81544 KB n=500
58 Correct 72 ms 81556 KB n=500
59 Correct 109 ms 83492 KB n=2000
60 Correct 110 ms 83676 KB n=2000
61 Correct 96 ms 83748 KB n=2000
62 Correct 97 ms 83816 KB n=2000
63 Correct 95 ms 83872 KB n=2000
64 Correct 99 ms 84068 KB n=2000
65 Correct 94 ms 84068 KB n=2000
66 Correct 94 ms 84240 KB n=2000
67 Correct 95 ms 84240 KB n=2000
68 Correct 97 ms 84240 KB n=2000
69 Correct 93 ms 84240 KB n=2000
70 Correct 81 ms 84240 KB n=2000
71 Correct 77 ms 84240 KB n=2000
72 Correct 80 ms 84260 KB n=2000
73 Correct 84 ms 84348 KB n=2000
74 Correct 93 ms 84372 KB n=1844
75 Correct 80 ms 84516 KB n=2000
76 Correct 97 ms 84516 KB n=2000
77 Correct 99 ms 84652 KB n=2000
78 Correct 102 ms 84652 KB n=2000
79 Correct 91 ms 84756 KB n=2000
80 Correct 109 ms 85000 KB n=2000
81 Correct 94 ms 85000 KB n=2000
82 Correct 95 ms 85000 KB n=2000
83 Correct 95 ms 85000 KB n=2000
84 Correct 96 ms 85000 KB n=2000
85 Correct 98 ms 85072 KB n=2000
86 Correct 95 ms 85100 KB n=2000
87 Correct 100 ms 85100 KB n=2000
88 Correct 95 ms 85252 KB n=2000
89 Correct 99 ms 85292 KB n=2000
90 Correct 96 ms 85348 KB n=2000
91 Correct 79 ms 85348 KB n=2000
92 Execution timed out 4110 ms 262144 KB Time limit exceeded
93 Halted 0 ms 0 KB -