oj.uz

Submission #342118

# Submission time Handle Problem Language Result Execution time Memory
342118 2021-01-01T11:51:01 Z maskoff Birthday gift (IZhO18_treearray) C++14
100 / 100
 1390 ms 109804 KB 
#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 3e5 + 5;

int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

int up[N][20], timer;
int tin[N], tout[N];
int n, m, q, c[N];
vector<int> g[N];
set<int> s[N], all[N];
            
void dfs(int x, int pr) {
 	up[x][0] = pr;
 	tin[x] = timer++;
 	for (int i = 1; i <= 18; i++)
 		up[x][i] = up[up[x][i - 1]][i - 1];
 	for (int to : g[x])
 		if (to != pr)
 			dfs(to, x);
 	tout[x] = timer++;
}

bool upper(int x, int y) {
 	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int lca(int x, int y) {
 	if (upper(x, y)) return x;
 	if (upper(y, x)) return y;
 	for (int i = 18; i >= 0; i--)
 		if (!upper(up[x][i], y) && up[x][i])
 			x = up[x][i];
	return up[x][0];
}             

void update() {
 	int pos, val;
 	cin >> pos >> val;
 	
 	int p = c[pos];

 	all[p].erase(pos);
 	all[val].insert(pos);

 	c[pos] = val;
 	
 	if (m == 1) return;

 	if (pos == m) {
 		int v = lca(c[m - 1], p);
 	 	s[v].erase(m - 1);
 	 	v = lca(c[m - 1], c[m]);
 	 	s[v].insert(m - 1);
 	}

 	else if (pos == 1) {
 	 	int v = lca(p, c[2]);
 	 	s[v].erase(1);
 	 	v = lca(c[1], c[2]);
 	 	s[v].insert(1);

 	} else {
 	 	int v = lca(p, c[pos - 1]);
 	 	s[v].erase(pos - 1);
 	 	v = lca(c[pos], c[pos - 1]);
 	 	s[v].insert(pos - 1);
 	 	v = lca(c[pos + 1], p);
 	 	s[v].erase(pos);
 	 	v = lca(c[pos + 1], c[pos]);
 	 	s[v].insert(pos);
 	}
}

void get() {
	int l, r, v;
	cin >> l >> r >> v;
	auto pos = *s[v].upper_bound(l - 1);
	if (pos < r) {
		cout << pos << " " << pos + 1 << endl;
		return;		
 	}
 	pos = *all[v].upper_bound(l - 1);
 	if (pos <= r) {
 	 	cout << pos << " " << pos << endl;
 	 	return;
 	}
 	cout << "-1 -1\n";
}                              

int main() { 
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		s[i].insert(m + 1), all[i].insert(m + 1);
	for (int i = 1; i < n; i++) {
	 	int x, y;
	 	cin >> x >> y;
	 	g[x].pb(y);
	 	g[y].pb(x);
	}
	dfs(1, 0);
	for (int i = 1; i <= m; i++) cin >> c[i];
	for (int i = 1; i <= m; i++)
		all[c[i]].insert(i);
	for (int i = 1; i < m; i++) 
		s[lca(c[i], c[i + 1])].insert(i);
	
	while (q--) {
   	int t;
   	cin >> t;
   	if (t == 1) update();
   	if (t == 2) get();
  }
  return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35564 KB n=5
2 Correct 26 ms 35564 KB n=100
3 Correct 24 ms 35564 KB n=100
4 Correct 24 ms 35564 KB n=100
5 Correct 25 ms 35692 KB n=100
6 Correct 25 ms 35564 KB n=100
7 Correct 25 ms 35564 KB n=100
8 Correct 25 ms 35692 KB n=100
9 Correct 26 ms 35564 KB n=100
10 Correct 25 ms 35564 KB n=100
11 Correct 24 ms 35564 KB n=100
12 Correct 26 ms 35564 KB n=100
13 Correct 24 ms 35564 KB n=100
14 Correct 24 ms 35564 KB n=100
15 Correct 25 ms 35564 KB n=100
16 Correct 24 ms 35564 KB n=100
17 Correct 24 ms 35564 KB n=100
18 Correct 26 ms 35564 KB n=100
19 Correct 24 ms 35564 KB n=100
20 Correct 24 ms 35564 KB n=100
21 Correct 24 ms 35564 KB n=100
22 Correct 26 ms 35564 KB n=100
23 Correct 24 ms 35584 KB n=100
24 Correct 25 ms 35564 KB n=100
25 Correct 24 ms 35564 KB n=100
26 Correct 24 ms 35564 KB n=12
27 Correct 25 ms 35564 KB n=100
28 Correct 26 ms 35820 KB n=500
29 Correct 25 ms 35820 KB n=500
30 Correct 25 ms 35820 KB n=500
31 Correct 25 ms 35820 KB n=500
32 Correct 25 ms 35820 KB n=500
33 Correct 25 ms 35840 KB n=500
34 Correct 25 ms 35820 KB n=500
35 Correct 26 ms 35948 KB n=500
36 Correct 26 ms 35692 KB n=500
37 Correct 26 ms 35692 KB n=500
38 Correct 26 ms 35692 KB n=500
39 Correct 25 ms 35820 KB n=500
40 Correct 25 ms 35820 KB n=500
41 Correct 24 ms 35820 KB n=500
42 Correct 25 ms 35692 KB n=500
43 Correct 26 ms 35692 KB n=500
44 Correct 27 ms 35692 KB n=500
45 Correct 26 ms 35820 KB n=500
46 Correct 25 ms 35820 KB n=500
47 Correct 25 ms 35820 KB n=500
48 Correct 25 ms 35820 KB n=500
49 Correct 25 ms 35820 KB n=500
50 Correct 25 ms 35820 KB n=500
51 Correct 26 ms 35820 KB n=500
52 Correct 26 ms 35820 KB n=500
53 Correct 27 ms 35820 KB n=500
54 Correct 25 ms 35820 KB n=500
55 Correct 25 ms 35692 KB n=278
56 Correct 25 ms 35820 KB n=500
57 Correct 25 ms 35820 KB n=500
58 Correct 25 ms 35820 KB n=500
59 Correct 30 ms 36332 KB n=2000
60 Correct 29 ms 36332 KB n=2000
61 Correct 29 ms 36332 KB n=2000
62 Correct 32 ms 36332 KB n=2000
63 Correct 30 ms 36332 KB n=2000
64 Correct 31 ms 36332 KB n=2000
65 Correct 30 ms 36332 KB n=2000
66 Correct 29 ms 36332 KB n=2000
67 Correct 30 ms 36204 KB n=2000
68 Correct 30 ms 36460 KB n=2000
69 Correct 32 ms 36332 KB n=2000
70 Correct 31 ms 36332 KB n=2000
71 Correct 31 ms 36332 KB n=2000
72 Correct 27 ms 36220 KB n=2000
73 Correct 27 ms 36332 KB n=2000
74 Correct 31 ms 36204 KB n=1844
75 Correct 27 ms 36332 KB n=2000
76 Correct 31 ms 36204 KB n=2000
77 Correct 31 ms 36204 KB n=2000
78 Correct 31 ms 36204 KB n=2000
79 Correct 30 ms 36204 KB n=2000
80 Correct 30 ms 36332 KB n=2000
81 Correct 30 ms 36460 KB n=2000
82 Correct 30 ms 36204 KB n=2000
83 Correct 29 ms 36332 KB n=2000
84 Correct 29 ms 36352 KB n=2000
85 Correct 29 ms 36332 KB n=2000
86 Correct 29 ms 36332 KB n=2000
87 Correct 29 ms 36332 KB n=2000
88 Correct 27 ms 36332 KB n=2000
89 Correct 27 ms 36332 KB n=2000
90 Correct 30 ms 36460 KB n=2000
91 Correct 30 ms 36460 KB n=2000
92 Correct 1095 ms 101244 KB n=200000
93 Correct 1151 ms 104940 KB n=200000
94 Correct 969 ms 108268 KB n=200000
95 Correct 1062 ms 101088 KB n=200000
96 Correct 1090 ms 101088 KB n=200000
97 Correct 1256 ms 104052 KB n=200000
98 Correct 1130 ms 101148 KB n=200000
99 Correct 1313 ms 100644 KB n=200000
100 Correct 1121 ms 101144 KB n=200000
101 Correct 930 ms 109672 KB n=200000
102 Correct 971 ms 102108 KB n=200000
103 Correct 989 ms 102064 KB n=200000
104 Correct 984 ms 102116 KB n=200000
105 Correct 962 ms 101868 KB n=200000
106 Correct 972 ms 102016 KB n=200000
107 Correct 973 ms 102020 KB n=200000
108 Correct 1182 ms 100972 KB n=200000
109 Correct 1226 ms 100972 KB n=200000
110 Correct 1215 ms 101008 KB n=200000
111 Correct 1076 ms 101216 KB n=200000
112 Correct 921 ms 108552 KB n=200000
113 Correct 1189 ms 104052 KB n=200000
114 Correct 1093 ms 101216 KB n=200000
115 Correct 1390 ms 102000 KB n=200000
116 Correct 925 ms 100964 KB n=200000
117 Correct 815 ms 109036 KB n=200000
118 Correct 1183 ms 103000 KB n=200000
119 Correct 911 ms 101216 KB n=200000
120 Correct 675 ms 109196 KB n=200000
121 Correct 674 ms 109420 KB n=200000
122 Correct 838 ms 109804 KB n=200000
123 Correct 769 ms 101484 KB n=200000
124 Correct 278 ms 52076 KB n=25264