oj.uz

Submission #379420

# Submission time Handle Problem Language Result Execution time Memory
379420 2021-03-18T08:02:53 Z cheissmart Birthday gift (IZhO18_treearray) C++14
100 / 100
 1168 ms 82796 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

int a[N], l[N];
set<int> where[N], where2[N];
vi G[N];

int p[N][20], d[N];

void dfs(int u, int pa = 0, int depth = 0) {
	p[u][0] = pa;
	for(int i = 1; i < 20; i++)
		p[u][i] = p[p[u][i - 1]][i - 1];
	d[u] = depth;
	for(int v:G[u]) if(v != pa)
		dfs(v, u, depth + 1);
}

int lca(int u, int v) {
	if(d[u] > d[v]) swap(u, v);
	for(int i = 19; i >= 0; i--)
		if((d[v] - d[u]) >> i & 1)
			v = p[v][i];
	if(u == v) return u;
	for(int i = 19; i >= 0; i--)
		if(p[u][i] != p[v][i])
			u = p[u][i], v = p[v][i];
	return p[u][0];
}

signed main()
{
	IO_OP;
	
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		G[u].PB(v);
		G[v].PB(u);
	}
	dfs(1);
	for(int i = 1; i <= m; i++) {
		cin >> a[i];
		where2[a[i]].insert(i);
	}
	auto del = [&] (int pos) {
		where[l[pos]].erase(pos);
	};
	auto calc = [&] (int pos) {
		l[pos] = lca(a[pos], a[pos + 1]);
		where[l[pos]].insert(pos);
	};
	for(int i = 1; i < m; i++) calc(i);
	while(q--) {
		int op;
		cin >> op;
		if(op == 1) {
			int pos, v;
			cin >> pos >> v;
			where2[a[pos]].erase(pos);
			a[pos] = v;
			where2[a[pos]].insert(pos);
			if(pos - 1 >= 1) {
				del(pos - 1);
				calc(pos - 1);
			}
			if(pos + 1 <= m) {
				del(pos);
				calc(pos);
			}
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			auto it = where[v].lower_bound(l);
			if(it != where[v].end() && *it < r) {
				cout << *it << " " << *it + 1 << '\n';
			} else {
				auto it = where2[v].lower_bound(l);
				if(it != where2[v].end() && *it <= r)
					cout << *it << ' ' << *it << '\n';
				else
					cout << -1 << " " << -1 << '\n';
			}
		}
	}

}

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 18 ms 23916 KB n=100
4 Correct 17 ms 23916 KB n=100
5 Correct 16 ms 23916 KB n=100
6 Correct 17 ms 23916 KB n=100
7 Correct 16 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 18 ms 23916 KB n=100
12 Correct 17 ms 23916 KB n=100
13 Correct 17 ms 23916 KB n=100
14 Correct 19 ms 23916 KB n=100
15 Correct 18 ms 23916 KB n=100
16 Correct 18 ms 23916 KB n=100
17 Correct 18 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 19 ms 23916 KB n=100
20 Correct 17 ms 23920 KB n=100
21 Correct 18 ms 23924 KB n=100
22 Correct 16 ms 23916 KB n=100
23 Correct 16 ms 23916 KB n=100
24 Correct 16 ms 23916 KB n=100
25 Correct 16 ms 23916 KB n=100
26 Correct 19 ms 23916 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 18 ms 23916 KB n=100
4 Correct 17 ms 23916 KB n=100
5 Correct 16 ms 23916 KB n=100
6 Correct 17 ms 23916 KB n=100
7 Correct 16 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 18 ms 23916 KB n=100
12 Correct 17 ms 23916 KB n=100
13 Correct 17 ms 23916 KB n=100
14 Correct 19 ms 23916 KB n=100
15 Correct 18 ms 23916 KB n=100
16 Correct 18 ms 23916 KB n=100
17 Correct 18 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 19 ms 23916 KB n=100
20 Correct 17 ms 23920 KB n=100
21 Correct 18 ms 23924 KB n=100
22 Correct 16 ms 23916 KB n=100
23 Correct 16 ms 23916 KB n=100
24 Correct 16 ms 23916 KB n=100
25 Correct 16 ms 23916 KB n=100
26 Correct 19 ms 23916 KB n=12
27 Correct 16 ms 23916 KB n=100
28 Correct 17 ms 23916 KB n=500
29 Correct 18 ms 23936 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 18 ms 23916 KB n=500
34 Correct 18 ms 23916 KB n=500
35 Correct 17 ms 24044 KB n=500
36 Correct 19 ms 23936 KB n=500
37 Correct 17 ms 23916 KB n=500
38 Correct 17 ms 23916 KB n=500
39 Correct 17 ms 23916 KB n=500
40 Correct 19 ms 23916 KB n=500
41 Correct 19 ms 23916 KB n=500
42 Correct 19 ms 23916 KB n=500
43 Correct 18 ms 23984 KB n=500
44 Correct 17 ms 23916 KB n=500
45 Correct 17 ms 23916 KB n=500
46 Correct 18 ms 24044 KB n=500
47 Correct 19 ms 23916 KB n=500
48 Correct 18 ms 24028 KB n=500
49 Correct 18 ms 24044 KB n=500
50 Correct 18 ms 23916 KB n=500
51 Correct 18 ms 23916 KB n=500
52 Correct 17 ms 24044 KB n=500
53 Correct 18 ms 23916 KB n=500
54 Correct 17 ms 24044 KB n=500
55 Correct 17 ms 23916 KB n=278
56 Correct 17 ms 24044 KB n=500
57 Correct 17 ms 24044 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 18 ms 23916 KB n=100
4 Correct 17 ms 23916 KB n=100
5 Correct 16 ms 23916 KB n=100
6 Correct 17 ms 23916 KB n=100
7 Correct 16 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 18 ms 23916 KB n=100
12 Correct 17 ms 23916 KB n=100
13 Correct 17 ms 23916 KB n=100
14 Correct 19 ms 23916 KB n=100
15 Correct 18 ms 23916 KB n=100
16 Correct 18 ms 23916 KB n=100
17 Correct 18 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 19 ms 23916 KB n=100
20 Correct 17 ms 23920 KB n=100
21 Correct 18 ms 23924 KB n=100
22 Correct 16 ms 23916 KB n=100
23 Correct 16 ms 23916 KB n=100
24 Correct 16 ms 23916 KB n=100
25 Correct 16 ms 23916 KB n=100
26 Correct 19 ms 23916 KB n=12
27 Correct 16 ms 23916 KB n=100
28 Correct 17 ms 23916 KB n=500
29 Correct 18 ms 23936 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 18 ms 23916 KB n=500
34 Correct 18 ms 23916 KB n=500
35 Correct 17 ms 24044 KB n=500
36 Correct 19 ms 23936 KB n=500
37 Correct 17 ms 23916 KB n=500
38 Correct 17 ms 23916 KB n=500
39 Correct 17 ms 23916 KB n=500
40 Correct 19 ms 23916 KB n=500
41 Correct 19 ms 23916 KB n=500
42 Correct 19 ms 23916 KB n=500
43 Correct 18 ms 23984 KB n=500
44 Correct 17 ms 23916 KB n=500
45 Correct 17 ms 23916 KB n=500
46 Correct 18 ms 24044 KB n=500
47 Correct 19 ms 23916 KB n=500
48 Correct 18 ms 24028 KB n=500
49 Correct 18 ms 24044 KB n=500
50 Correct 18 ms 23916 KB n=500
51 Correct 18 ms 23916 KB n=500
52 Correct 17 ms 24044 KB n=500
53 Correct 18 ms 23916 KB n=500
54 Correct 17 ms 24044 KB n=500
55 Correct 17 ms 23916 KB n=278
56 Correct 17 ms 24044 KB n=500
57 Correct 17 ms 24044 KB n=500
58 Correct 17 ms 23916 KB n=500
59 Correct 20 ms 24300 KB n=2000
60 Correct 20 ms 24428 KB n=2000
61 Correct 20 ms 24428 KB n=2000
62 Correct 22 ms 24300 KB n=2000
63 Correct 20 ms 24300 KB n=2000
64 Correct 21 ms 24428 KB n=2000
65 Correct 20 ms 24300 KB n=2000
66 Correct 20 ms 24428 KB n=2000
67 Correct 21 ms 24300 KB n=2000
68 Correct 20 ms 24428 KB n=2000
69 Correct 19 ms 24300 KB n=2000
70 Correct 21 ms 24300 KB n=2000
71 Correct 22 ms 24300 KB n=2000
72 Correct 19 ms 24300 KB n=2000
73 Correct 21 ms 24300 KB n=2000
74 Correct 22 ms 24300 KB n=1844
75 Correct 19 ms 24300 KB n=2000
76 Correct 20 ms 24300 KB n=2000
77 Correct 20 ms 24300 KB n=2000
78 Correct 20 ms 24300 KB n=2000
79 Correct 21 ms 24300 KB n=2000
80 Correct 20 ms 24428 KB n=2000
81 Correct 24 ms 24428 KB n=2000
82 Correct 20 ms 24300 KB n=2000
83 Correct 20 ms 24428 KB n=2000
84 Correct 20 ms 24300 KB n=2000
85 Correct 21 ms 24428 KB n=2000
86 Correct 20 ms 24300 KB n=2000
87 Correct 20 ms 24300 KB n=2000
88 Correct 19 ms 24428 KB n=2000
89 Correct 20 ms 24428 KB n=2000
90 Correct 20 ms 24428 KB n=2000
91 Correct 20 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 18 ms 23916 KB n=100
4 Correct 17 ms 23916 KB n=100
5 Correct 16 ms 23916 KB n=100
6 Correct 17 ms 23916 KB n=100
7 Correct 16 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 18 ms 23916 KB n=100
12 Correct 17 ms 23916 KB n=100
13 Correct 17 ms 23916 KB n=100
14 Correct 19 ms 23916 KB n=100
15 Correct 18 ms 23916 KB n=100
16 Correct 18 ms 23916 KB n=100
17 Correct 18 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 19 ms 23916 KB n=100
20 Correct 17 ms 23920 KB n=100
21 Correct 18 ms 23924 KB n=100
22 Correct 16 ms 23916 KB n=100
23 Correct 16 ms 23916 KB n=100
24 Correct 16 ms 23916 KB n=100
25 Correct 16 ms 23916 KB n=100
26 Correct 19 ms 23916 KB n=12
27 Correct 16 ms 23916 KB n=100
28 Correct 17 ms 23916 KB n=500
29 Correct 18 ms 23936 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 18 ms 23916 KB n=500
34 Correct 18 ms 23916 KB n=500
35 Correct 17 ms 24044 KB n=500
36 Correct 19 ms 23936 KB n=500
37 Correct 17 ms 23916 KB n=500
38 Correct 17 ms 23916 KB n=500
39 Correct 17 ms 23916 KB n=500
40 Correct 19 ms 23916 KB n=500
41 Correct 19 ms 23916 KB n=500
42 Correct 19 ms 23916 KB n=500
43 Correct 18 ms 23984 KB n=500
44 Correct 17 ms 23916 KB n=500
45 Correct 17 ms 23916 KB n=500
46 Correct 18 ms 24044 KB n=500
47 Correct 19 ms 23916 KB n=500
48 Correct 18 ms 24028 KB n=500
49 Correct 18 ms 24044 KB n=500
50 Correct 18 ms 23916 KB n=500
51 Correct 18 ms 23916 KB n=500
52 Correct 17 ms 24044 KB n=500
53 Correct 18 ms 23916 KB n=500
54 Correct 17 ms 24044 KB n=500
55 Correct 17 ms 23916 KB n=278
56 Correct 17 ms 24044 KB n=500
57 Correct 17 ms 24044 KB n=500
58 Correct 17 ms 23916 KB n=500
59 Correct 20 ms 24300 KB n=2000
60 Correct 20 ms 24428 KB n=2000
61 Correct 20 ms 24428 KB n=2000
62 Correct 22 ms 24300 KB n=2000
63 Correct 20 ms 24300 KB n=2000
64 Correct 21 ms 24428 KB n=2000
65 Correct 20 ms 24300 KB n=2000
66 Correct 20 ms 24428 KB n=2000
67 Correct 21 ms 24300 KB n=2000
68 Correct 20 ms 24428 KB n=2000
69 Correct 19 ms 24300 KB n=2000
70 Correct 21 ms 24300 KB n=2000
71 Correct 22 ms 24300 KB n=2000
72 Correct 19 ms 24300 KB n=2000
73 Correct 21 ms 24300 KB n=2000
74 Correct 22 ms 24300 KB n=1844
75 Correct 19 ms 24300 KB n=2000
76 Correct 20 ms 24300 KB n=2000
77 Correct 20 ms 24300 KB n=2000
78 Correct 20 ms 24300 KB n=2000
79 Correct 21 ms 24300 KB n=2000
80 Correct 20 ms 24428 KB n=2000
81 Correct 24 ms 24428 KB n=2000
82 Correct 20 ms 24300 KB n=2000
83 Correct 20 ms 24428 KB n=2000
84 Correct 20 ms 24300 KB n=2000
85 Correct 21 ms 24428 KB n=2000
86 Correct 20 ms 24300 KB n=2000
87 Correct 20 ms 24300 KB n=2000
88 Correct 19 ms 24428 KB n=2000
89 Correct 20 ms 24428 KB n=2000
90 Correct 20 ms 24428 KB n=2000
91 Correct 20 ms 24300 KB n=2000
92 Correct 806 ms 72704 KB n=200000
93 Correct 1027 ms 77788 KB n=200000
94 Correct 961 ms 81132 KB n=200000
95 Correct 763 ms 72800 KB n=200000
96 Correct 800 ms 72772 KB n=200000
97 Correct 1105 ms 77012 KB n=200000
98 Correct 764 ms 72804 KB n=200000
99 Correct 1002 ms 73068 KB n=200000
100 Correct 813 ms 72932 KB n=200000
101 Correct 948 ms 82412 KB n=200000
102 Correct 515 ms 74092 KB n=200000
103 Correct 503 ms 74052 KB n=200000
104 Correct 504 ms 73996 KB n=200000
105 Correct 526 ms 74504 KB n=200000
106 Correct 511 ms 74436 KB n=200000
107 Correct 524 ms 74476 KB n=200000
108 Correct 869 ms 73196 KB n=200000
109 Correct 900 ms 73836 KB n=200000
110 Correct 890 ms 73748 KB n=200000
111 Correct 815 ms 73316 KB n=200000
112 Correct 939 ms 81444 KB n=200000
113 Correct 1016 ms 76852 KB n=200000
114 Correct 796 ms 73312 KB n=200000
115 Correct 1168 ms 74732 KB n=200000
116 Correct 742 ms 73824 KB n=200000
117 Correct 961 ms 81900 KB n=200000
118 Correct 1048 ms 75628 KB n=200000
119 Correct 696 ms 73824 KB n=200000
120 Correct 885 ms 82156 KB n=200000
121 Correct 901 ms 82284 KB n=200000
122 Correct 881 ms 82796 KB n=200000
123 Correct 511 ms 74348 KB n=200000
124 Correct 232 ms 39148 KB n=25264