oj.uz

Submission #1024188

# Submission time Handle Problem Language Result Execution time Memory
1024188 2024-07-15T15:18:28 Z Acanikolic Birthday gift (IZhO18_treearray) C++14
100 / 100
 619 ms 98316 KB 
#include <bits/stdc++.h>  

#define int long long 

#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const int N = 2e5 + 10;
 
const int mod = 1e9 + 7;
 
const int inf = 1e9;

const int LOG = 17;

vector<int>g[N];
int up[N][LOG],in[N],out[N],timer = 0,a[N],m;
set<int>st[N][2];

void dfs(int x,int par) {
	in[x] = ++timer;
	up[x][0] = par;
	for(int j = 1; j < LOG; j++) up[x][j] = up[up[x][j - 1]][j - 1];
	for(auto X : g[x]) {
		if(X != par) {
			dfs(X,x);
		}
	}
	out[x] = timer;
}

bool inn(int u,int v) {
	return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u,int v) {
	if(u == inf) return v;
	if(v == inf) return u;
	if(inn(u,v)) return u;
	if(inn(v,u)) return v;
	for(int j = LOG - 1; j >= 0; j--) {
		if(up[u][j] > 0 && !inn(up[u][j],v)) u = up[u][j];
	}
	return up[u][0];
}

void add(int i,bool o) {
	if(i < 1) return;
	if(!o) {
		st[a[i]][0].insert(i);
		return;
	}
	if(i + 1 <= m) {
		st[lca(a[i],a[i + 1])][1].insert(i);
	}
}

void rem(int i,bool o) {
	if(i < 1) return;
	if(!o) {
		st[a[i]][0].erase(i);
		return;
	}
	if(i + 1 <= m) {
		st[lca(a[i],a[i + 1])][1].erase(i);
	}
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 	int n,q;
 	cin >> n >> m >> q;
 	for(int i = 1; i <= n - 1; i++) {
 		int u,v;
 		cin >> u >> v;
 		g[u].pb(v);
 		g[v].pb(u);
 	}
 	dfs(1,0);
 	for(int i = 1; i <= m; i++) cin >> a[i];
 	for(int i = 1; i <= m; i++) add(i,0);
 	for(int i = 1; i + 1 <= m; i++) add(i,1);
 	while(q--) {
 		int type;
 		cin >> type;
 		if(type == 1) {
 			int i,v;
 			cin >> i >> v;
 			rem(i - 1,0);
 			rem(i - 1,1);
 			rem(i,0);
 			rem(i,1);
 			a[i] = v;
 			add(i - 1,0);
 			add(i - 1,1);
 			add(i,0);
 			add(i,1);
 		}else {
 			int l,r,v;
 			cin >> l >> r >> v;
 			int L = -1,R = -1;
 			auto lb = st[v][0].lower_bound(l);
 			if(lb != st[v][0].end() && *lb <= r) L = *lb,R = *lb;
 			auto rb = st[v][1].lower_bound(l);
 			if(rb != st[v][1].end() && *rb < r) L = *rb,R = *rb + 1;
 			cout << L << " " << R << "\n";
 		}
 	}
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30556 KB n=5
2 Correct 4 ms 30556 KB n=100
3 Correct 5 ms 30556 KB n=100
4 Correct 4 ms 30552 KB n=100
5 Correct 6 ms 30556 KB n=100
6 Correct 5 ms 30552 KB n=100
7 Correct 5 ms 30556 KB n=100
8 Correct 5 ms 30556 KB n=100
9 Correct 5 ms 30556 KB n=100
10 Correct 5 ms 30552 KB n=100
11 Correct 5 ms 30556 KB n=100
12 Correct 5 ms 30552 KB n=100
13 Correct 6 ms 30552 KB n=100
14 Correct 5 ms 30556 KB n=100
15 Correct 5 ms 30556 KB n=100
16 Correct 5 ms 30640 KB n=100
17 Correct 5 ms 30552 KB n=100
18 Correct 5 ms 30556 KB n=100
19 Correct 4 ms 30552 KB n=100
20 Correct 5 ms 30556 KB n=100
21 Correct 5 ms 30644 KB n=100
22 Correct 5 ms 30556 KB n=100
23 Correct 4 ms 30556 KB n=100
24 Correct 4 ms 30556 KB n=100
25 Correct 4 ms 30556 KB n=100
26 Correct 4 ms 30556 KB n=12
27 Correct 5 ms 30556 KB n=100
28 Correct 5 ms 30556 KB n=500
29 Correct 5 ms 30552 KB n=500
30 Correct 6 ms 30556 KB n=500
31 Correct 6 ms 30556 KB n=500
32 Correct 5 ms 30556 KB n=500
33 Correct 5 ms 30552 KB n=500
34 Correct 5 ms 30712 KB n=500
35 Correct 5 ms 30556 KB n=500
36 Correct 5 ms 30552 KB n=500
37 Correct 5 ms 30556 KB n=500
38 Correct 5 ms 30556 KB n=500
39 Correct 5 ms 30556 KB n=500
40 Correct 6 ms 30556 KB n=500
41 Correct 5 ms 30552 KB n=500
42 Correct 6 ms 30820 KB n=500
43 Correct 6 ms 30556 KB n=500
44 Correct 5 ms 30556 KB n=500
45 Correct 6 ms 30556 KB n=500
46 Correct 5 ms 30552 KB n=500
47 Correct 6 ms 30556 KB n=500
48 Correct 5 ms 30556 KB n=500
49 Correct 6 ms 30556 KB n=500
50 Correct 5 ms 30556 KB n=500
51 Correct 5 ms 30556 KB n=500
52 Correct 7 ms 30556 KB n=500
53 Correct 5 ms 30556 KB n=500
54 Correct 5 ms 30556 KB n=500
55 Correct 5 ms 30556 KB n=278
56 Correct 5 ms 30552 KB n=500
57 Correct 6 ms 30552 KB n=500
58 Correct 5 ms 30552 KB n=500
59 Correct 7 ms 30808 KB n=2000
60 Correct 7 ms 31008 KB n=2000
61 Correct 7 ms 30808 KB n=2000
62 Correct 7 ms 30812 KB n=2000
63 Correct 7 ms 30812 KB n=2000
64 Correct 7 ms 30812 KB n=2000
65 Correct 7 ms 30812 KB n=2000
66 Correct 6 ms 30808 KB n=2000
67 Correct 7 ms 30808 KB n=2000
68 Correct 8 ms 30812 KB n=2000
69 Correct 7 ms 30812 KB n=2000
70 Correct 6 ms 30808 KB n=2000
71 Correct 7 ms 30812 KB n=2000
72 Correct 7 ms 30812 KB n=2000
73 Correct 7 ms 30812 KB n=2000
74 Correct 7 ms 30812 KB n=1844
75 Correct 6 ms 30812 KB n=2000
76 Correct 7 ms 30812 KB n=2000
77 Correct 8 ms 30812 KB n=2000
78 Correct 7 ms 30812 KB n=2000
79 Correct 7 ms 30812 KB n=2000
80 Correct 6 ms 30812 KB n=2000
81 Correct 7 ms 30812 KB n=2000
82 Correct 7 ms 30812 KB n=2000
83 Correct 6 ms 31000 KB n=2000
84 Correct 8 ms 30812 KB n=2000
85 Correct 7 ms 30812 KB n=2000
86 Correct 7 ms 30812 KB n=2000
87 Correct 7 ms 30808 KB n=2000
88 Correct 7 ms 30812 KB n=2000
89 Correct 6 ms 30808 KB n=2000
90 Correct 7 ms 30812 KB n=2000
91 Correct 6 ms 30812 KB n=2000
92 Correct 447 ms 89548 KB n=200000
93 Correct 511 ms 94288 KB n=200000
94 Correct 374 ms 97364 KB n=200000
95 Correct 430 ms 89280 KB n=200000
96 Correct 419 ms 89232 KB n=200000
97 Correct 541 ms 93484 KB n=200000
98 Correct 427 ms 89280 KB n=200000
99 Correct 452 ms 89680 KB n=200000
100 Correct 424 ms 89288 KB n=200000
101 Correct 317 ms 98316 KB n=200000
102 Correct 244 ms 90712 KB n=200000
103 Correct 228 ms 90708 KB n=200000
104 Correct 228 ms 90704 KB n=200000
105 Correct 226 ms 91204 KB n=200000
106 Correct 232 ms 90964 KB n=200000
107 Correct 237 ms 91216 KB n=200000
108 Correct 502 ms 89656 KB n=200000
109 Correct 515 ms 89684 KB n=200000
110 Correct 544 ms 89636 KB n=200000
111 Correct 508 ms 88744 KB n=200000
112 Correct 402 ms 97364 KB n=200000
113 Correct 574 ms 93448 KB n=200000
114 Correct 439 ms 88904 KB n=200000
115 Correct 619 ms 91488 KB n=200000
116 Correct 418 ms 89520 KB n=200000
117 Correct 333 ms 97688 KB n=200000
118 Correct 607 ms 92320 KB n=200000
119 Correct 394 ms 89532 KB n=200000
120 Correct 285 ms 97104 KB n=200000
121 Correct 292 ms 97096 KB n=200000
122 Correct 266 ms 97364 KB n=200000
123 Correct 252 ms 90812 KB n=200000
124 Correct 84 ms 45176 KB n=25264