oj.uz

Submission #334911

# Submission time Handle Problem Language Result Execution time Memory
334911 2020-12-10T08:42:11 Z tengiz05 Birthday gift (IZhO18_treearray) C++17
100 / 100
 1222 ms 80776 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int n, m, k;
vector<int> edges[N];
int tin[N], tout[N];
int up[N][20];
int timer;
void dfs(int u, int p, int d=0){
	tin[u] = timer++;
	up[u][0] = p;
	for(int i=1;i<19;i++)up[u][i] = up[up[u][i-1]][i-1];
	for(auto v : edges[u]){
		if(v != p){
			dfs(v, u,d+1);
		}
	}tout[u] = timer++;
}
bool isancestor(int u, int v){
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
	if(isancestor(u,v))return u;
	if(isancestor(v,u))return v;
	for(int i=18;i>=0;i--){
		if(!isancestor(up[u][i], v))u = up[u][i];
	}return up[u][0];
}
int a[N]; 
set<int> lc[N];
set<int> ar[N];
void solve(int test_case){
	int i, j, q;
	cin >> n >> m >> q;
	for(i=1;i<n;i++){
		int u, v;
		cin >> u >> v;
		edges[u].pb(v);
		edges[v].pb(u);
	}dfs(1,1);
	for(i=1;i<=m;i++){
		cin >> a[i];
		ar[a[i]].insert(i);
	}
	for(i=1;i<m;i++){
		lc[lca(a[i], a[i+1])].insert(i);
	}
	while(q--){
		int type;
		cin >> type;
		if(type == 1){
			int pos, val;
			cin >> pos >> val;
			ar[a[pos]].erase(pos);
			ar[val].insert(pos);
			if(pos > 1)lc[lca(a[pos], a[pos-1])].erase(pos-1);
			if(pos < m)lc[lca(a[pos], a[pos+1])].erase(pos);
			a[pos] = val;
			if(pos > 1)lc[lca(a[pos], a[pos-1])].insert(pos-1);
			if(pos < m)lc[lca(a[pos], a[pos+1])].insert(pos);
		}else {
			int l, r, v;
			cin >> l >> r >> v;
			auto x = ar[v].lower_bound(l);
			int ansl=-1, ansr=-1;
			if(x != ar[v].end() && *x <= r){
				ansl = ansr = *x;
			}
			auto y = lc[v].lower_bound(l);
			if(y != lc[v].end() && *y < r){
				ansl = (*y);
				ansr = (*y)+1;
			}
			cout << ansl << ' ' << ansr << '\n';
		}
	}
	return;
}
 
signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

treearray.cpp: In function 'void solve(int)':
treearray.cpp:43:9: warning: unused variable 'j' [-Wunused-variable]
   43 |  int i, j, q;
      |         ^

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB n=5
2 Correct 16 ms 23916 KB n=100
3 Correct 17 ms 23916 KB n=100
4 Correct 17 ms 23916 KB n=100
5 Correct 17 ms 23916 KB n=100
6 Correct 16 ms 23916 KB n=100
7 Correct 20 ms 23916 KB n=100
8 Correct 16 ms 23916 KB n=100
9 Correct 16 ms 23916 KB n=100
10 Correct 16 ms 23916 KB n=100
11 Correct 16 ms 23916 KB n=100
12 Correct 16 ms 23916 KB n=100
13 Correct 18 ms 23916 KB n=100
14 Correct 18 ms 23916 KB n=100
15 Correct 16 ms 23880 KB n=100
16 Correct 17 ms 23916 KB n=100
17 Correct 16 ms 23916 KB n=100
18 Correct 17 ms 23916 KB n=100
19 Correct 16 ms 23916 KB n=100
20 Correct 17 ms 23916 KB n=100
21 Correct 16 ms 23916 KB n=100
22 Correct 16 ms 23916 KB n=100
23 Correct 17 ms 23916 KB n=100
24 Correct 16 ms 23916 KB n=100
25 Correct 16 ms 23916 KB n=100
26 Correct 16 ms 23788 KB n=12
27 Correct 16 ms 23916 KB n=100
28 Correct 17 ms 23916 KB n=500
29 Correct 17 ms 23916 KB n=500
30 Correct 17 ms 23916 KB n=500
31 Correct 17 ms 23916 KB n=500
32 Correct 18 ms 23916 KB n=500
33 Correct 17 ms 23916 KB n=500
34 Correct 19 ms 23916 KB n=500
35 Correct 17 ms 23916 KB n=500
36 Correct 17 ms 23916 KB n=500
37 Correct 18 ms 23916 KB n=500
38 Correct 17 ms 23916 KB n=500
39 Correct 17 ms 23916 KB n=500
40 Correct 17 ms 23916 KB n=500
41 Correct 17 ms 23916 KB n=500
42 Correct 18 ms 23916 KB n=500
43 Correct 18 ms 23916 KB n=500
44 Correct 17 ms 23916 KB n=500
45 Correct 17 ms 23916 KB n=500
46 Correct 17 ms 23916 KB n=500
47 Correct 17 ms 23916 KB n=500
48 Correct 17 ms 23916 KB n=500
49 Correct 17 ms 23916 KB n=500
50 Correct 19 ms 23916 KB n=500
51 Correct 17 ms 23916 KB n=500
52 Correct 17 ms 23916 KB n=500
53 Correct 17 ms 23916 KB n=500
54 Correct 18 ms 23916 KB n=500
55 Correct 17 ms 23916 KB n=278
56 Correct 17 ms 23916 KB n=500
57 Correct 17 ms 23916 KB n=500
58 Correct 17 ms 23916 KB n=500
59 Correct 20 ms 24300 KB n=2000
60 Correct 19 ms 24428 KB n=2000
61 Correct 20 ms 24300 KB n=2000
62 Correct 20 ms 24300 KB n=2000
63 Correct 21 ms 24300 KB n=2000
64 Correct 20 ms 24300 KB n=2000
65 Correct 21 ms 24300 KB n=2000
66 Correct 20 ms 24300 KB n=2000
67 Correct 21 ms 24300 KB n=2000
68 Correct 20 ms 24300 KB n=2000
69 Correct 19 ms 24300 KB n=2000
70 Correct 19 ms 24300 KB n=2000
71 Correct 19 ms 24300 KB n=2000
72 Correct 20 ms 24300 KB n=2000
73 Correct 19 ms 24428 KB n=2000
74 Correct 20 ms 24300 KB n=1844
75 Correct 19 ms 24300 KB n=2000
76 Correct 21 ms 24428 KB n=2000
77 Correct 22 ms 24332 KB n=2000
78 Correct 21 ms 24300 KB n=2000
79 Correct 20 ms 24300 KB n=2000
80 Correct 19 ms 24428 KB n=2000
81 Correct 20 ms 24300 KB n=2000
82 Correct 21 ms 24300 KB n=2000
83 Correct 19 ms 24300 KB n=2000
84 Correct 20 ms 24300 KB n=2000
85 Correct 20 ms 24300 KB n=2000
86 Correct 20 ms 24300 KB n=2000
87 Correct 20 ms 24300 KB n=2000
88 Correct 20 ms 24428 KB n=2000
89 Correct 19 ms 24428 KB n=2000
90 Correct 19 ms 24428 KB n=2000
91 Correct 19 ms 24300 KB n=2000
92 Correct 837 ms 68972 KB n=200000
93 Correct 933 ms 74476 KB n=200000
94 Correct 705 ms 78796 KB n=200000
95 Correct 808 ms 69088 KB n=200000
96 Correct 839 ms 68960 KB n=200000
97 Correct 1010 ms 73428 KB n=200000
98 Correct 824 ms 69088 KB n=200000
99 Correct 1000 ms 68332 KB n=200000
100 Correct 832 ms 69220 KB n=200000
101 Correct 637 ms 80492 KB n=200000
102 Correct 505 ms 70124 KB n=200000
103 Correct 499 ms 69868 KB n=200000
104 Correct 507 ms 69996 KB n=200000
105 Correct 509 ms 69868 KB n=200000
106 Correct 503 ms 69868 KB n=200000
107 Correct 503 ms 69740 KB n=200000
108 Correct 880 ms 68716 KB n=200000
109 Correct 878 ms 68716 KB n=200000
110 Correct 894 ms 68588 KB n=200000
111 Correct 888 ms 69044 KB n=200000
112 Correct 704 ms 79340 KB n=200000
113 Correct 996 ms 73400 KB n=200000
114 Correct 883 ms 69216 KB n=200000
115 Correct 1222 ms 70508 KB n=200000
116 Correct 776 ms 68832 KB n=200000
117 Correct 650 ms 79852 KB n=200000
118 Correct 1088 ms 71788 KB n=200000
119 Correct 767 ms 68756 KB n=200000
120 Correct 591 ms 80236 KB n=200000
121 Correct 589 ms 80364 KB n=200000
122 Correct 596 ms 80776 KB n=200000
123 Correct 527 ms 69396 KB n=200000
124 Correct 200 ms 37484 KB n=25264