oj.uz

Submission #585948

# Submission time Handle Problem Language Result Execution time Memory
585948 2022-06-29T15:20:37 Z Zanite Birthday gift (IZhO18_treearray) C++17
100 / 100
 739 ms 130932 KB 
// I am now here, but I have yet to prove that I am worthy of my place here.

#include <bits/stdc++.h>
using namespace std;

using pii	= pair<int, int>;

#define fi first
#define se second

const int maxN	= 2e5 + 5;
const int logN	= 21;

int n, m, q, a[maxN];

vector<int> adj[maxN];
int tin[maxN], tout[maxN], depth[maxN];
vector<int> Euler;

set<pii> seg[maxN];

struct SparseTable {
	int s;
	vector<vector<pii>> ST;

	void build() {
		s = Euler.size();

		ST.push_back(vector<pii>(0));
		for (auto i : Euler) {
			ST[0].push_back({depth[i], i});
		}

		for (int i = 1; i < logN; i++) {
			ST.push_back(vector<pii>(s));

			for (int j = 0; j <= s - (1 << i); j++) {
				ST[i][j] = min(ST[i-1][j], ST[i-1][j + (1 << (i-1))]);
			}
		}
	}

	pii query(int l, int r) {
		int d = r - l + 1;
		int t = 31 - __builtin_clz(d);

		return min(ST[t][l], ST[t][r - (1 << t) + 1]);
	}

	void print() {
		for (auto i : ST) {
			for (auto j : i) {
				printf("{%d, %d} ", j.fi, j.se);
			}
			printf("\n");
		}
	}
} TreeData;

void dfs(int cur, int par, int dpt) {
	Euler.push_back(cur);
	tin[cur] = Euler.size()-1;
	depth[cur] = dpt;

	for (auto nxt : adj[cur]) {
		if (nxt == par) continue;
		dfs(nxt, cur, dpt+1);
		Euler.push_back(cur);
	}

	tout[cur] = Euler.size()-1;
}

int LCA(int x, int y) {
	//cerr << "LCA " << x << " " << y << '\n';
	if (x == 0) return y;
	if (y == 0) return x;
	if (tin[x] > tin[y]) swap(x, y);
	return TreeData.query(tin[x], tin[y]).se;
}

int main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int u, v, i = 1; i < n; i++) {
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0, 0);
	TreeData.build();

	for (int i = 1; i <= m; i++) {
		scanf("%d", &a[i]);
	}

	// create segments
	for (int i = 1; i <= m; i++) {
		seg[a[i]].insert({i, i});
	}
	for (int i = 1; i < m; i++) {
		seg[LCA(a[i], a[i+1])].insert({i, i+1});
	}

	for (int typ, pos, l, r, v, i = 1; i <= q; i++) {
		scanf("%d", &typ);

		if (typ == 1) {
			scanf("%d %d", &pos, &v);

			seg[a[pos]].erase({pos, pos});
			if (pos > 1) {seg[LCA(a[pos-1], a[pos])].erase({pos-1, pos});}
			if (pos < m) {seg[LCA(a[pos], a[pos+1])].erase({pos, pos+1});}

			a[pos] = v;
			
			seg[a[pos]].insert({pos, pos});
			if (pos > 1) {seg[LCA(a[pos-1], a[pos])].insert({pos-1, pos});}
			if (pos < m) {seg[LCA(a[pos], a[pos+1])].insert({pos, pos+1});}

		} else {
			scanf("%d %d %d", &l, &r, &v);
			pii ans = {-1, -1};
			
			auto it = seg[v].lower_bound({l, -1});
			if (it != seg[v].end()) {
				int xl, xr;
				tie(xl, xr) = *it;
				if (l <= xl && xl <= r && l <= xr && xr <= r) ans = *it;
			}

			printf("%d %d\n", ans.fi, ans.se);

		}
	}
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
treearray.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf("%d", &typ);
      |   ~~~~~^~~~~~~~~~~~
treearray.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |    scanf("%d %d", &pos, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:121:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |    scanf("%d %d %d", &l, &r, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB n=5
2 Correct 9 ms 14420 KB n=100
3 Correct 8 ms 14420 KB n=100
4 Correct 8 ms 14424 KB n=100
5 Correct 8 ms 14408 KB n=100
6 Correct 8 ms 14408 KB n=100
7 Correct 8 ms 14444 KB n=100
8 Correct 8 ms 14420 KB n=100
9 Correct 8 ms 14420 KB n=100
10 Correct 9 ms 14420 KB n=100
11 Correct 9 ms 14412 KB n=100
12 Correct 7 ms 14420 KB n=100
13 Correct 8 ms 14404 KB n=100
14 Correct 8 ms 14420 KB n=100
15 Correct 9 ms 14420 KB n=100
16 Correct 8 ms 14420 KB n=100
17 Correct 9 ms 14392 KB n=100
18 Correct 9 ms 14404 KB n=100
19 Correct 8 ms 14408 KB n=100
20 Correct 8 ms 14420 KB n=100
21 Correct 8 ms 14456 KB n=100
22 Correct 8 ms 14420 KB n=100
23 Correct 8 ms 14428 KB n=100
24 Correct 8 ms 14420 KB n=100
25 Correct 8 ms 14412 KB n=100
26 Correct 8 ms 14544 KB n=12
27 Correct 8 ms 14408 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB n=5
2 Correct 9 ms 14420 KB n=100
3 Correct 8 ms 14420 KB n=100
4 Correct 8 ms 14424 KB n=100
5 Correct 8 ms 14408 KB n=100
6 Correct 8 ms 14408 KB n=100
7 Correct 8 ms 14444 KB n=100
8 Correct 8 ms 14420 KB n=100
9 Correct 8 ms 14420 KB n=100
10 Correct 9 ms 14420 KB n=100
11 Correct 9 ms 14412 KB n=100
12 Correct 7 ms 14420 KB n=100
13 Correct 8 ms 14404 KB n=100
14 Correct 8 ms 14420 KB n=100
15 Correct 9 ms 14420 KB n=100
16 Correct 8 ms 14420 KB n=100
17 Correct 9 ms 14392 KB n=100
18 Correct 9 ms 14404 KB n=100
19 Correct 8 ms 14408 KB n=100
20 Correct 8 ms 14420 KB n=100
21 Correct 8 ms 14456 KB n=100
22 Correct 8 ms 14420 KB n=100
23 Correct 8 ms 14428 KB n=100
24 Correct 8 ms 14420 KB n=100
25 Correct 8 ms 14412 KB n=100
26 Correct 8 ms 14544 KB n=12
27 Correct 8 ms 14408 KB n=100
28 Correct 10 ms 14548 KB n=500
29 Correct 8 ms 14676 KB n=500
30 Correct 8 ms 14676 KB n=500
31 Correct 8 ms 14676 KB n=500
32 Correct 9 ms 14548 KB n=500
33 Correct 9 ms 14676 KB n=500
34 Correct 9 ms 14624 KB n=500
35 Correct 8 ms 14676 KB n=500
36 Correct 9 ms 14672 KB n=500
37 Correct 8 ms 14600 KB n=500
38 Correct 9 ms 14548 KB n=500
39 Correct 8 ms 14676 KB n=500
40 Correct 8 ms 14548 KB n=500
41 Correct 8 ms 14676 KB n=500
42 Correct 9 ms 14548 KB n=500
43 Correct 9 ms 14548 KB n=500
44 Correct 9 ms 14644 KB n=500
45 Correct 8 ms 14548 KB n=500
46 Correct 9 ms 14688 KB n=500
47 Correct 8 ms 14676 KB n=500
48 Correct 9 ms 14540 KB n=500
49 Correct 8 ms 14676 KB n=500
50 Correct 8 ms 14548 KB n=500
51 Correct 8 ms 14676 KB n=500
52 Correct 9 ms 14676 KB n=500
53 Correct 9 ms 14676 KB n=500
54 Correct 8 ms 14676 KB n=500
55 Correct 9 ms 14536 KB n=278
56 Correct 9 ms 14676 KB n=500
57 Correct 8 ms 14596 KB n=500
58 Correct 8 ms 14612 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB n=5
2 Correct 9 ms 14420 KB n=100
3 Correct 8 ms 14420 KB n=100
4 Correct 8 ms 14424 KB n=100
5 Correct 8 ms 14408 KB n=100
6 Correct 8 ms 14408 KB n=100
7 Correct 8 ms 14444 KB n=100
8 Correct 8 ms 14420 KB n=100
9 Correct 8 ms 14420 KB n=100
10 Correct 9 ms 14420 KB n=100
11 Correct 9 ms 14412 KB n=100
12 Correct 7 ms 14420 KB n=100
13 Correct 8 ms 14404 KB n=100
14 Correct 8 ms 14420 KB n=100
15 Correct 9 ms 14420 KB n=100
16 Correct 8 ms 14420 KB n=100
17 Correct 9 ms 14392 KB n=100
18 Correct 9 ms 14404 KB n=100
19 Correct 8 ms 14408 KB n=100
20 Correct 8 ms 14420 KB n=100
21 Correct 8 ms 14456 KB n=100
22 Correct 8 ms 14420 KB n=100
23 Correct 8 ms 14428 KB n=100
24 Correct 8 ms 14420 KB n=100
25 Correct 8 ms 14412 KB n=100
26 Correct 8 ms 14544 KB n=12
27 Correct 8 ms 14408 KB n=100
28 Correct 10 ms 14548 KB n=500
29 Correct 8 ms 14676 KB n=500
30 Correct 8 ms 14676 KB n=500
31 Correct 8 ms 14676 KB n=500
32 Correct 9 ms 14548 KB n=500
33 Correct 9 ms 14676 KB n=500
34 Correct 9 ms 14624 KB n=500
35 Correct 8 ms 14676 KB n=500
36 Correct 9 ms 14672 KB n=500
37 Correct 8 ms 14600 KB n=500
38 Correct 9 ms 14548 KB n=500
39 Correct 8 ms 14676 KB n=500
40 Correct 8 ms 14548 KB n=500
41 Correct 8 ms 14676 KB n=500
42 Correct 9 ms 14548 KB n=500
43 Correct 9 ms 14548 KB n=500
44 Correct 9 ms 14644 KB n=500
45 Correct 8 ms 14548 KB n=500
46 Correct 9 ms 14688 KB n=500
47 Correct 8 ms 14676 KB n=500
48 Correct 9 ms 14540 KB n=500
49 Correct 8 ms 14676 KB n=500
50 Correct 8 ms 14548 KB n=500
51 Correct 8 ms 14676 KB n=500
52 Correct 9 ms 14676 KB n=500
53 Correct 9 ms 14676 KB n=500
54 Correct 8 ms 14676 KB n=500
55 Correct 9 ms 14536 KB n=278
56 Correct 9 ms 14676 KB n=500
57 Correct 8 ms 14596 KB n=500
58 Correct 8 ms 14612 KB n=500
59 Correct 13 ms 15412 KB n=2000
60 Correct 11 ms 15468 KB n=2000
61 Correct 10 ms 15444 KB n=2000
62 Correct 12 ms 15444 KB n=2000
63 Correct 12 ms 15420 KB n=2000
64 Correct 11 ms 15444 KB n=2000
65 Correct 10 ms 15316 KB n=2000
66 Correct 10 ms 15444 KB n=2000
67 Correct 11 ms 15320 KB n=2000
68 Correct 11 ms 15412 KB n=2000
69 Correct 11 ms 15444 KB n=2000
70 Correct 10 ms 15444 KB n=2000
71 Correct 11 ms 15444 KB n=2000
72 Correct 12 ms 15556 KB n=2000
73 Correct 11 ms 15316 KB n=2000
74 Correct 10 ms 15316 KB n=1844
75 Correct 10 ms 15444 KB n=2000
76 Correct 11 ms 15316 KB n=2000
77 Correct 11 ms 15312 KB n=2000
78 Correct 12 ms 15316 KB n=2000
79 Correct 12 ms 15316 KB n=2000
80 Correct 11 ms 15520 KB n=2000
81 Correct 11 ms 15444 KB n=2000
82 Correct 11 ms 15436 KB n=2000
83 Correct 11 ms 15400 KB n=2000
84 Correct 11 ms 15448 KB n=2000
85 Correct 11 ms 15444 KB n=2000
86 Correct 11 ms 15444 KB n=2000
87 Correct 11 ms 15312 KB n=2000
88 Correct 11 ms 15444 KB n=2000
89 Correct 11 ms 15556 KB n=2000
90 Correct 12 ms 15444 KB n=2000
91 Correct 11 ms 15444 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB n=5
2 Correct 9 ms 14420 KB n=100
3 Correct 8 ms 14420 KB n=100
4 Correct 8 ms 14424 KB n=100
5 Correct 8 ms 14408 KB n=100
6 Correct 8 ms 14408 KB n=100
7 Correct 8 ms 14444 KB n=100
8 Correct 8 ms 14420 KB n=100
9 Correct 8 ms 14420 KB n=100
10 Correct 9 ms 14420 KB n=100
11 Correct 9 ms 14412 KB n=100
12 Correct 7 ms 14420 KB n=100
13 Correct 8 ms 14404 KB n=100
14 Correct 8 ms 14420 KB n=100
15 Correct 9 ms 14420 KB n=100
16 Correct 8 ms 14420 KB n=100
17 Correct 9 ms 14392 KB n=100
18 Correct 9 ms 14404 KB n=100
19 Correct 8 ms 14408 KB n=100
20 Correct 8 ms 14420 KB n=100
21 Correct 8 ms 14456 KB n=100
22 Correct 8 ms 14420 KB n=100
23 Correct 8 ms 14428 KB n=100
24 Correct 8 ms 14420 KB n=100
25 Correct 8 ms 14412 KB n=100
26 Correct 8 ms 14544 KB n=12
27 Correct 8 ms 14408 KB n=100
28 Correct 10 ms 14548 KB n=500
29 Correct 8 ms 14676 KB n=500
30 Correct 8 ms 14676 KB n=500
31 Correct 8 ms 14676 KB n=500
32 Correct 9 ms 14548 KB n=500
33 Correct 9 ms 14676 KB n=500
34 Correct 9 ms 14624 KB n=500
35 Correct 8 ms 14676 KB n=500
36 Correct 9 ms 14672 KB n=500
37 Correct 8 ms 14600 KB n=500
38 Correct 9 ms 14548 KB n=500
39 Correct 8 ms 14676 KB n=500
40 Correct 8 ms 14548 KB n=500
41 Correct 8 ms 14676 KB n=500
42 Correct 9 ms 14548 KB n=500
43 Correct 9 ms 14548 KB n=500
44 Correct 9 ms 14644 KB n=500
45 Correct 8 ms 14548 KB n=500
46 Correct 9 ms 14688 KB n=500
47 Correct 8 ms 14676 KB n=500
48 Correct 9 ms 14540 KB n=500
49 Correct 8 ms 14676 KB n=500
50 Correct 8 ms 14548 KB n=500
51 Correct 8 ms 14676 KB n=500
52 Correct 9 ms 14676 KB n=500
53 Correct 9 ms 14676 KB n=500
54 Correct 8 ms 14676 KB n=500
55 Correct 9 ms 14536 KB n=278
56 Correct 9 ms 14676 KB n=500
57 Correct 8 ms 14596 KB n=500
58 Correct 8 ms 14612 KB n=500
59 Correct 13 ms 15412 KB n=2000
60 Correct 11 ms 15468 KB n=2000
61 Correct 10 ms 15444 KB n=2000
62 Correct 12 ms 15444 KB n=2000
63 Correct 12 ms 15420 KB n=2000
64 Correct 11 ms 15444 KB n=2000
65 Correct 10 ms 15316 KB n=2000
66 Correct 10 ms 15444 KB n=2000
67 Correct 11 ms 15320 KB n=2000
68 Correct 11 ms 15412 KB n=2000
69 Correct 11 ms 15444 KB n=2000
70 Correct 10 ms 15444 KB n=2000
71 Correct 11 ms 15444 KB n=2000
72 Correct 12 ms 15556 KB n=2000
73 Correct 11 ms 15316 KB n=2000
74 Correct 10 ms 15316 KB n=1844
75 Correct 10 ms 15444 KB n=2000
76 Correct 11 ms 15316 KB n=2000
77 Correct 11 ms 15312 KB n=2000
78 Correct 12 ms 15316 KB n=2000
79 Correct 12 ms 15316 KB n=2000
80 Correct 11 ms 15520 KB n=2000
81 Correct 11 ms 15444 KB n=2000
82 Correct 11 ms 15436 KB n=2000
83 Correct 11 ms 15400 KB n=2000
84 Correct 11 ms 15448 KB n=2000
85 Correct 11 ms 15444 KB n=2000
86 Correct 11 ms 15444 KB n=2000
87 Correct 11 ms 15312 KB n=2000
88 Correct 11 ms 15444 KB n=2000
89 Correct 11 ms 15556 KB n=2000
90 Correct 12 ms 15444 KB n=2000
91 Correct 11 ms 15444 KB n=2000
92 Correct 686 ms 115536 KB n=200000
93 Correct 653 ms 124772 KB n=200000
94 Correct 627 ms 129384 KB n=200000
95 Correct 661 ms 118088 KB n=200000
96 Correct 657 ms 118156 KB n=200000
97 Correct 676 ms 123776 KB n=200000
98 Correct 675 ms 118232 KB n=200000
99 Correct 738 ms 118380 KB n=200000
100 Correct 717 ms 118268 KB n=200000
101 Correct 620 ms 130932 KB n=200000
102 Correct 391 ms 119448 KB n=200000
103 Correct 390 ms 119472 KB n=200000
104 Correct 385 ms 119408 KB n=200000
105 Correct 391 ms 119836 KB n=200000
106 Correct 387 ms 119984 KB n=200000
107 Correct 385 ms 119968 KB n=200000
108 Correct 667 ms 118356 KB n=200000
109 Correct 659 ms 118276 KB n=200000
110 Correct 676 ms 118244 KB n=200000
111 Correct 642 ms 117692 KB n=200000
112 Correct 603 ms 129652 KB n=200000
113 Correct 687 ms 123552 KB n=200000
114 Correct 653 ms 117840 KB n=200000
115 Correct 739 ms 120840 KB n=200000
116 Correct 645 ms 118480 KB n=200000
117 Correct 611 ms 130276 KB n=200000
118 Correct 700 ms 122168 KB n=200000
119 Correct 669 ms 118380 KB n=200000
120 Correct 578 ms 129980 KB n=200000
121 Correct 584 ms 130136 KB n=200000
122 Correct 573 ms 130360 KB n=200000
123 Correct 401 ms 119604 KB n=200000
124 Correct 162 ms 36324 KB n=25264