oj.uz

Submission #336282

# Submission time Handle Problem Language Result Execution time Memory
336282 2020-12-15T03:43:15 Z super_j6 Birthday gift (IZhO18_treearray) C++14
56 / 100
 4000 ms 254584 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define f first
#define s second

const int mxn = 200000, k = __lg(mxn - 1) + 1, w = 900;
int n, m, q;
int a[mxn], lc[mxn], d[mxn];
int p[k][mxn];
vector<int> g[mxn];

void dfs(int c){
	for(int i = 1; i < k; i++) p[i][c] = ~p[i][c] ? p[i - 1][p[i - 1][c]] : -1;
	for(int i : g[c]) if(i != p[0][c]) d[i] = d[c] + 1, p[0][i] = c, dfs(i);
}

int lca(int x, int y){
	if(d[x] < d[y]) swap(x, y);
	for(int i = k - 1; ~i; i--) if(~p[i][x] && d[p[i][x]] >= d[y]) x = p[i][x];
	for(int i = k - 1; ~i; i--) if(p[i][x] != p[i][y]) x = p[i][x], y = p[i][y];
	return x == y ? x : p[0][x];
}

struct segTree{
	int l, r;
	segTree *tl, *tr;
	set<pii> s;
	
	segTree(int l, int r) : l(l), r(r){
		for(int i = l; i <= r; i++){
			s.insert({a[i], {i, i}});
			if(i < r) s.insert({lc[i], {i, i + 1}});
		}
		if(r - l > w){
			int mid = (l + r) / 2;
			tl = new segTree(l, mid);
			tr = new segTree(mid + 1, r);
		}
	}
	
	void add(int x){
		if(x < l || r < x) return;
		s.insert({a[x], {x, x}});
		if(x > l) s.insert({lc[x - 1], {x - 1, x}});
		if(x < r) s.insert({lc[x], {x, x + 1}});
		if(r - l <= w) return;
		tl->add(x), tr->add(x);
	}
	
	void del(int x){
		if(x < l || r < x) return;
		s.erase({a[x], {x, x}});
		if(x > l) s.erase({lc[x - 1], {x - 1, x}});
		if(x < r) s.erase({lc[x], {x, x + 1}});
		if(r - l <= w) return;
		tl->del(x), tr->del(x);
	}
	
	pi qry(int x, int y, int v){
		if(y < l || r < x) return {-2, -2};
		if(x <= l && r <= y){
			auto it = s.lower_bound({v, {0, 0}});
			return it != s.end() && it->f == v ? it->s : pi{-2, -2};
		}
		if(r - l <= w){
			for(int i = max(l, x); i <= min(r, y); i++){
				if(a[i] == v) return {i, i};
				if(i < min(r, y) && lc[i] == v) return {i, i + 1};
			}
			return {-2, -2};
		}
		int mid = (l + r) / 2;
		if(x <= mid && mid + 1 <= y && lc[mid] == v){
			return {mid, mid + 1};
		} 
		pi p = tl->qry(x, y, v);
		if(p.f != -2) return p;
		return tr->qry(x, y, v);
	}
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	p[0][0] = -1;
	dfs(0);
	
	for(int i = 0; i < m; i++){
		cin >> a[i], a[i]--;
		if(i) lc[i - 1] = lca(a[i - 1], a[i]);
	} 
	
	segTree tre(0, m - 1);
	while(q--){
		int t;
		cin >> t;
		if(t & 1){
			int x, y;
			cin >> x >> y;
			x--, y--;
			tre.del(x);
			a[x] = y;
			if(x) lc[x - 1] = lca(a[x - 1], a[x]);
			if(x < m - 1) lc[x] = lca(a[x], a[x + 1]);
			tre.add(x);
		}else{
			int l, r, x;
			cin >> l >> r >> x;
			pi p = tre.qry(--l, --r, --x);
			cout << p.f + 1 << " " << p.s + 1 << endl;
		}
	}

	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
0 / 44.0

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