oj.uz

Submission #338539

# Submission time Handle Problem Language Result Execution time Memory
338539 2020-12-23T10:46:42 Z shivensinha4 Birthday gift (IZhO18_treearray) C++17
100 / 100
 1202 ms 141592 KB 
#include "bits/stdc++.h"
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
 
class SparseTable {
	vector<vector<ii>> st;
	vi log; vector<ii> raw;
	int n;
 
	void computeLog() {
		log.resize(n+1, -1);
		int p = 0, two_pow = 1;
		while (two_pow <= n) {
			log[two_pow] = p++;
			two_pow *= 2;
		}
		int prev = 0;
		for_(i, 1, n+1) {
			if (log[i] != -1) prev = log[i];
			else log[i] = prev;
		}
	}
 
	void buildTable() {
		int k = log[n]+1;
		st.resize(n, vector<ii> (k));
		for_(i, 0, n) st[i][0] = raw[i];
		for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1) 
			st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]);
	}
 
	public:
	void build(vector<ii> nums) {
		raw = nums;
		n = nums.size();
		computeLog();
		buildTable();
	}
 
	int mn(int l, int r) {
		if (l > r) swap(l, r);
		int p = log[r-l+1];
		return min(st[l][p], st[r - (1<<p) + 1][p]).second;
	}
};
 
SparseTable st;
vector<vi> adj;
vector<ii> tour;
vi tin, tout;
 
void dfs(int p, int d, int parent) {
	tin[p] = tour.size();
	tour.push_back({d, p});
	for (int i: adj[p]) if (i != parent) {
		dfs(i, d+1, p);
		tour.push_back({d, p});
	}
	
	tin[p] = tour.size()-1;
}
 
int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, q; cin >> n >> m >> q;
	adj.resize(n); tin.resize(n); tout.resize(n);
	for_(i, 0, n-1) {
		int a, b; cin >> a >> b;
		a -= 1; b -= 1;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	
	dfs(0, 0, 0);
	st.build(tour);
	
	vi nums(m);
	vector<multiset<int>> pos(n);
 
	for_(i, 0, m) {
		cin >> nums[i]; nums[i]--;
		pos[nums[i]].insert(i);
	}
	
	for_(i, 0, m-1) {
		pos[st.mn(tin[nums[i]], tin[nums[i+1]])].insert(i);
	}
	
	for_(_, 0, q) {
		int t; cin >> t;
		if (t == 1) {
			int i, v; cin >> i >> v;
			v -= 1; i -= 1;
			if (i > 0) {
				pos[st.mn(tin[nums[i]], tin[nums[i-1]])].erase(pos[st.mn(tin[nums[i]], tin[nums[i-1]])].find(i-1));
				pos[st.mn(tin[v], tin[nums[i-1]])].insert(i-1);
			}
			if (i < m-1) {
				pos[st.mn(tin[nums[i]], tin[nums[i+1]])].erase(pos[st.mn(tin[nums[i]], tin[nums[i+1]])].find(i));
				pos[st.mn(tin[v], tin[nums[i+1]])].insert(i);
			}
			
			pos[nums[i]].erase(pos[nums[i]].find(i));
			nums[i] = v;
			pos[nums[i]].insert(i);
		} else {
			int l, r, v; cin >> l >> r >> v;
			v -= 1; l -= 1; r -= 1;
			auto pt = pos[v].lower_bound(l);
			int ansl = -2, ansr = -2;
			if (pt != pos[v].end() and *pt <= r) {
				int idx = *pt;
				if (nums[idx] == v) ansl = ansr = idx;
				else if (idx < r) {
					ansl = idx; ansr = idx+1;
				}
			}
			
			cout << ansl+1 << " " << ansr+1 << endl;
		}
	}
 
	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB n=5
2 Correct 1 ms 364 KB n=100
3 Correct 1 ms 364 KB n=100
4 Correct 1 ms 384 KB n=100
5 Correct 1 ms 364 KB n=100
6 Correct 1 ms 364 KB n=100
7 Correct 1 ms 364 KB n=100
8 Correct 1 ms 364 KB n=100
9 Correct 1 ms 384 KB n=100
10 Correct 1 ms 364 KB n=100
11 Correct 1 ms 364 KB n=100
12 Correct 1 ms 364 KB n=100
13 Correct 1 ms 364 KB n=100
14 Correct 1 ms 364 KB n=100
15 Correct 1 ms 364 KB n=100
16 Correct 1 ms 364 KB n=100
17 Correct 1 ms 364 KB n=100
18 Correct 1 ms 364 KB n=100
19 Correct 1 ms 364 KB n=100
20 Correct 1 ms 364 KB n=100
21 Correct 1 ms 364 KB n=100
22 Correct 1 ms 384 KB n=100
23 Correct 1 ms 364 KB n=100
24 Correct 1 ms 364 KB n=100
25 Correct 1 ms 364 KB n=100
26 Correct 1 ms 364 KB n=12
27 Correct 1 ms 364 KB n=100
28 Correct 2 ms 620 KB n=500
29 Correct 1 ms 640 KB n=500
30 Correct 1 ms 620 KB n=500
31 Correct 1 ms 620 KB n=500
32 Correct 1 ms 620 KB n=500
33 Correct 1 ms 620 KB n=500
34 Correct 1 ms 620 KB n=500
35 Correct 1 ms 620 KB n=500
36 Correct 1 ms 620 KB n=500
37 Correct 1 ms 620 KB n=500
38 Correct 1 ms 620 KB n=500
39 Correct 1 ms 620 KB n=500
40 Correct 1 ms 620 KB n=500
41 Correct 1 ms 620 KB n=500
42 Correct 1 ms 620 KB n=500
43 Correct 2 ms 620 KB n=500
44 Correct 1 ms 620 KB n=500
45 Correct 1 ms 620 KB n=500
46 Correct 1 ms 620 KB n=500
47 Correct 1 ms 620 KB n=500
48 Correct 1 ms 640 KB n=500
49 Correct 2 ms 620 KB n=500
50 Correct 2 ms 620 KB n=500
51 Correct 1 ms 620 KB n=500
52 Correct 1 ms 620 KB n=500
53 Correct 1 ms 620 KB n=500
54 Correct 2 ms 620 KB n=500
55 Correct 1 ms 492 KB n=278
56 Correct 1 ms 620 KB n=500
57 Correct 1 ms 620 KB n=500
58 Correct 2 ms 620 KB n=500
59 Correct 5 ms 1388 KB n=2000
60 Correct 4 ms 1516 KB n=2000
61 Correct 5 ms 1516 KB n=2000
62 Correct 5 ms 1388 KB n=2000
63 Correct 5 ms 1388 KB n=2000
64 Correct 4 ms 1388 KB n=2000
65 Correct 5 ms 1388 KB n=2000
66 Correct 4 ms 1516 KB n=2000
67 Correct 5 ms 1388 KB n=2000
68 Correct 4 ms 1516 KB n=2000
69 Correct 4 ms 1388 KB n=2000
70 Correct 4 ms 1388 KB n=2000
71 Correct 4 ms 1388 KB n=2000
72 Correct 4 ms 1388 KB n=2000
73 Correct 4 ms 1388 KB n=2000
74 Correct 4 ms 1260 KB n=1844
75 Correct 4 ms 1388 KB n=2000
76 Correct 5 ms 1388 KB n=2000
77 Correct 5 ms 1388 KB n=2000
78 Correct 5 ms 1388 KB n=2000
79 Correct 5 ms 1388 KB n=2000
80 Correct 4 ms 1516 KB n=2000
81 Correct 4 ms 1408 KB n=2000
82 Correct 5 ms 1388 KB n=2000
83 Correct 4 ms 1516 KB n=2000
84 Correct 4 ms 1388 KB n=2000
85 Correct 5 ms 1388 KB n=2000
86 Correct 5 ms 1388 KB n=2000
87 Correct 4 ms 1388 KB n=2000
88 Correct 4 ms 1516 KB n=2000
89 Correct 5 ms 1516 KB n=2000
90 Correct 4 ms 1516 KB n=2000
91 Correct 4 ms 1408 KB n=2000
92 Correct 1147 ms 123784 KB n=200000
93 Correct 1094 ms 132168 KB n=200000
94 Correct 1047 ms 139032 KB n=200000
95 Correct 1053 ms 123652 KB n=200000
96 Correct 1061 ms 123676 KB n=200000
97 Correct 1128 ms 130524 KB n=200000
98 Correct 1081 ms 123676 KB n=200000
99 Correct 1173 ms 123164 KB n=200000
100 Correct 1088 ms 123800 KB n=200000
101 Correct 1028 ms 141196 KB n=200000
102 Correct 665 ms 124576 KB n=200000
103 Correct 705 ms 124704 KB n=200000
104 Correct 655 ms 124644 KB n=200000
105 Correct 664 ms 124260 KB n=200000
106 Correct 679 ms 124320 KB n=200000
107 Correct 657 ms 124448 KB n=200000
108 Correct 1115 ms 123296 KB n=200000
109 Correct 1111 ms 123296 KB n=200000
110 Correct 1114 ms 123424 KB n=200000
111 Correct 1074 ms 123556 KB n=200000
112 Correct 1032 ms 139400 KB n=200000
113 Correct 1117 ms 130200 KB n=200000
114 Correct 1096 ms 123552 KB n=200000
115 Correct 1202 ms 126080 KB n=200000
116 Correct 1028 ms 123420 KB n=200000
117 Correct 1000 ms 140184 KB n=200000
118 Correct 1201 ms 128152 KB n=200000
119 Correct 986 ms 123292 KB n=200000
120 Correct 953 ms 141080 KB n=200000
121 Correct 972 ms 141300 KB n=200000
122 Correct 960 ms 141592 KB n=200000
123 Correct 713 ms 123932 KB n=200000
124 Correct 255 ms 23512 KB n=25264