oj.uz

Submission #876738

# Submission time Handle Problem Language Result Execution time Memory
876738 2023-11-22T09:16:52 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
100 / 100
 877 ms 113952 KB 
#include <bits/stdc++.h>
 
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define optimus_prime ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define fxd(x) fixed << setprecision(x)
#define all(a) (a.begin() , a.end())
#define popcount(x) __builtin_popcount(x)
#define lwb lower_bound
#define upb upper_bound
#define dl double long
#define ll long long
#define int long long
#define pb push_back
#define sz() size()
#define F first
#define S second
 
using namespace std;
 
const ll N = 2e5+9;
const ll L = 18;

ll n , m , q , a[N] , tin[N] , tout[N] , timer , up[N][L+9];
vector <int> g[N];
set <int> st[N] , st1[N];

void calc(ll cur , ll p){
	tin[cur]=++timer;
	up[cur][0]=p;
	for (int i = 1 ; i <= L ; i++)up[cur][i]=up[up[cur][i-1]][i-1];
	for (auto to : g[cur]){
		if (to!=p)calc(to , cur);
	}
	tout[cur]=timer;
}

bool upper(ll a , ll b){
	return (tin[a]<=tin[b]&&tout[b]<=tout[a]);
}

ll lca(ll a , ll b){
	if (a && (!b || upper(a , b)))return a;
	if (b && (!a || upper(b , a)))return b;
	for (int i = L ; i >= 0 ; i--){
		if (!up[a][i])continue;	
		if (!upper(up[a][i] , b))a=up[a][i];
	}
	return up[a][0];
}

void solve(){
	cin >> n >> m >> q;
	for (int i = 1 ; i < n ; i++){
		ll u , v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	calc(1 , 0);
	for (int i = 1 ; i <= m ; i++){
		cin >> a[i];
		st[a[i]].insert(i);
		if (i>1)st1[lca(a[i-1] , a[i])].insert(i-1);
	}
	while (q--){
		ll tp;
		cin >> tp;
		if (tp==1){
			ll pos , v;
			cin >> pos >> v;
			if (pos<m)st1[lca(a[pos] , a[pos+1])].erase(pos);
			if (pos>1)st1[lca(a[pos-1] , a[pos])].erase(pos-1);
			st[a[pos]].erase(pos);
			a[pos]=v;
			st[a[pos]].insert(pos);
			if (pos<m)st1[lca(a[pos] , a[pos+1])].insert(pos);
			if (pos>1)st1[lca(a[pos-1] , a[pos])].insert(pos-1);
		}
		else {
			ll l , r , v;
			cin >> l >> r >> v;
			if (st[v].lwb(l)!=st[v].end() && (*st[v].lwb(l))<=r){
				ll x=*(st[v].lwb(l));
				cout << x << " " << x << "\n";
			}
			else if (st1[v].lwb(l)!=st1[v].end() && (*st1[v].lwb(l))<r){
				ll x=*(st1[v].lwb(l));
				cout << x << " " << x+1 << "\n";
			}
			else cout << "-1 -1\n";
			
		}
	}
}
	
signed main() {
	optimus_prime;
	solve();
return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB n=5
2 Correct 6 ms 29276 KB n=100
3 Correct 6 ms 29532 KB n=100
4 Correct 6 ms 29280 KB n=100
5 Correct 6 ms 29284 KB n=100
6 Correct 6 ms 29280 KB n=100
7 Correct 6 ms 29348 KB n=100
8 Correct 6 ms 29324 KB n=100
9 Correct 7 ms 29284 KB n=100
10 Correct 6 ms 29364 KB n=100
11 Correct 6 ms 29284 KB n=100
12 Correct 6 ms 29284 KB n=100
13 Correct 6 ms 29320 KB n=100
14 Correct 7 ms 29288 KB n=100
15 Correct 7 ms 29356 KB n=100
16 Correct 6 ms 29284 KB n=100
17 Correct 6 ms 29284 KB n=100
18 Correct 6 ms 29288 KB n=100
19 Correct 7 ms 29276 KB n=100
20 Correct 5 ms 29276 KB n=100
21 Correct 7 ms 29536 KB n=100
22 Correct 6 ms 29276 KB n=100
23 Correct 5 ms 29284 KB n=100
24 Correct 6 ms 29280 KB n=100
25 Correct 6 ms 29280 KB n=100
26 Correct 6 ms 29272 KB n=12
27 Correct 7 ms 29276 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB n=5
2 Correct 6 ms 29276 KB n=100
3 Correct 6 ms 29532 KB n=100
4 Correct 6 ms 29280 KB n=100
5 Correct 6 ms 29284 KB n=100
6 Correct 6 ms 29280 KB n=100
7 Correct 6 ms 29348 KB n=100
8 Correct 6 ms 29324 KB n=100
9 Correct 7 ms 29284 KB n=100
10 Correct 6 ms 29364 KB n=100
11 Correct 6 ms 29284 KB n=100
12 Correct 6 ms 29284 KB n=100
13 Correct 6 ms 29320 KB n=100
14 Correct 7 ms 29288 KB n=100
15 Correct 7 ms 29356 KB n=100
16 Correct 6 ms 29284 KB n=100
17 Correct 6 ms 29284 KB n=100
18 Correct 6 ms 29288 KB n=100
19 Correct 7 ms 29276 KB n=100
20 Correct 5 ms 29276 KB n=100
21 Correct 7 ms 29536 KB n=100
22 Correct 6 ms 29276 KB n=100
23 Correct 5 ms 29284 KB n=100
24 Correct 6 ms 29280 KB n=100
25 Correct 6 ms 29280 KB n=100
26 Correct 6 ms 29272 KB n=12
27 Correct 7 ms 29276 KB n=100
28 Correct 7 ms 29272 KB n=500
29 Correct 6 ms 29272 KB n=500
30 Correct 6 ms 29368 KB n=500
31 Correct 7 ms 29416 KB n=500
32 Correct 6 ms 29276 KB n=500
33 Correct 6 ms 29276 KB n=500
34 Correct 8 ms 29456 KB n=500
35 Correct 6 ms 29276 KB n=500
36 Correct 6 ms 29276 KB n=500
37 Correct 7 ms 29272 KB n=500
38 Correct 6 ms 29276 KB n=500
39 Correct 6 ms 29272 KB n=500
40 Correct 6 ms 29272 KB n=500
41 Correct 6 ms 29276 KB n=500
42 Correct 7 ms 29276 KB n=500
43 Correct 6 ms 29272 KB n=500
44 Correct 6 ms 29276 KB n=500
45 Correct 6 ms 29272 KB n=500
46 Correct 6 ms 29276 KB n=500
47 Correct 7 ms 29272 KB n=500
48 Correct 7 ms 29276 KB n=500
49 Correct 6 ms 29272 KB n=500
50 Correct 6 ms 29276 KB n=500
51 Correct 7 ms 29276 KB n=500
52 Correct 7 ms 29480 KB n=500
53 Correct 6 ms 29284 KB n=500
54 Correct 6 ms 29320 KB n=500
55 Correct 6 ms 29288 KB n=278
56 Correct 6 ms 29280 KB n=500
57 Correct 7 ms 29276 KB n=500
58 Correct 7 ms 29272 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB n=5
2 Correct 6 ms 29276 KB n=100
3 Correct 6 ms 29532 KB n=100
4 Correct 6 ms 29280 KB n=100
5 Correct 6 ms 29284 KB n=100
6 Correct 6 ms 29280 KB n=100
7 Correct 6 ms 29348 KB n=100
8 Correct 6 ms 29324 KB n=100
9 Correct 7 ms 29284 KB n=100
10 Correct 6 ms 29364 KB n=100
11 Correct 6 ms 29284 KB n=100
12 Correct 6 ms 29284 KB n=100
13 Correct 6 ms 29320 KB n=100
14 Correct 7 ms 29288 KB n=100
15 Correct 7 ms 29356 KB n=100
16 Correct 6 ms 29284 KB n=100
17 Correct 6 ms 29284 KB n=100
18 Correct 6 ms 29288 KB n=100
19 Correct 7 ms 29276 KB n=100
20 Correct 5 ms 29276 KB n=100
21 Correct 7 ms 29536 KB n=100
22 Correct 6 ms 29276 KB n=100
23 Correct 5 ms 29284 KB n=100
24 Correct 6 ms 29280 KB n=100
25 Correct 6 ms 29280 KB n=100
26 Correct 6 ms 29272 KB n=12
27 Correct 7 ms 29276 KB n=100
28 Correct 7 ms 29272 KB n=500
29 Correct 6 ms 29272 KB n=500
30 Correct 6 ms 29368 KB n=500
31 Correct 7 ms 29416 KB n=500
32 Correct 6 ms 29276 KB n=500
33 Correct 6 ms 29276 KB n=500
34 Correct 8 ms 29456 KB n=500
35 Correct 6 ms 29276 KB n=500
36 Correct 6 ms 29276 KB n=500
37 Correct 7 ms 29272 KB n=500
38 Correct 6 ms 29276 KB n=500
39 Correct 6 ms 29272 KB n=500
40 Correct 6 ms 29272 KB n=500
41 Correct 6 ms 29276 KB n=500
42 Correct 7 ms 29276 KB n=500
43 Correct 6 ms 29272 KB n=500
44 Correct 6 ms 29276 KB n=500
45 Correct 6 ms 29272 KB n=500
46 Correct 6 ms 29276 KB n=500
47 Correct 7 ms 29272 KB n=500
48 Correct 7 ms 29276 KB n=500
49 Correct 6 ms 29272 KB n=500
50 Correct 6 ms 29276 KB n=500
51 Correct 7 ms 29276 KB n=500
52 Correct 7 ms 29480 KB n=500
53 Correct 6 ms 29284 KB n=500
54 Correct 6 ms 29320 KB n=500
55 Correct 6 ms 29288 KB n=278
56 Correct 6 ms 29280 KB n=500
57 Correct 7 ms 29276 KB n=500
58 Correct 7 ms 29272 KB n=500
59 Correct 8 ms 29536 KB n=2000
60 Correct 9 ms 29708 KB n=2000
61 Correct 8 ms 29744 KB n=2000
62 Correct 8 ms 29532 KB n=2000
63 Correct 8 ms 29568 KB n=2000
64 Correct 10 ms 29536 KB n=2000
65 Correct 8 ms 29532 KB n=2000
66 Correct 8 ms 29532 KB n=2000
67 Correct 9 ms 29712 KB n=2000
68 Correct 8 ms 29556 KB n=2000
69 Correct 8 ms 29728 KB n=2000
70 Correct 8 ms 29528 KB n=2000
71 Correct 8 ms 29616 KB n=2000
72 Correct 8 ms 29528 KB n=2000
73 Correct 8 ms 29532 KB n=2000
74 Correct 8 ms 29528 KB n=1844
75 Correct 8 ms 29532 KB n=2000
76 Correct 8 ms 29532 KB n=2000
77 Correct 9 ms 29532 KB n=2000
78 Correct 8 ms 29532 KB n=2000
79 Correct 10 ms 29772 KB n=2000
80 Correct 8 ms 29528 KB n=2000
81 Correct 8 ms 29528 KB n=2000
82 Correct 9 ms 29532 KB n=2000
83 Correct 8 ms 29532 KB n=2000
84 Correct 8 ms 29528 KB n=2000
85 Correct 8 ms 29528 KB n=2000
86 Correct 8 ms 29532 KB n=2000
87 Correct 8 ms 29688 KB n=2000
88 Correct 8 ms 29788 KB n=2000
89 Correct 8 ms 29724 KB n=2000
90 Correct 8 ms 29784 KB n=2000
91 Correct 8 ms 29532 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB n=5
2 Correct 6 ms 29276 KB n=100
3 Correct 6 ms 29532 KB n=100
4 Correct 6 ms 29280 KB n=100
5 Correct 6 ms 29284 KB n=100
6 Correct 6 ms 29280 KB n=100
7 Correct 6 ms 29348 KB n=100
8 Correct 6 ms 29324 KB n=100
9 Correct 7 ms 29284 KB n=100
10 Correct 6 ms 29364 KB n=100
11 Correct 6 ms 29284 KB n=100
12 Correct 6 ms 29284 KB n=100
13 Correct 6 ms 29320 KB n=100
14 Correct 7 ms 29288 KB n=100
15 Correct 7 ms 29356 KB n=100
16 Correct 6 ms 29284 KB n=100
17 Correct 6 ms 29284 KB n=100
18 Correct 6 ms 29288 KB n=100
19 Correct 7 ms 29276 KB n=100
20 Correct 5 ms 29276 KB n=100
21 Correct 7 ms 29536 KB n=100
22 Correct 6 ms 29276 KB n=100
23 Correct 5 ms 29284 KB n=100
24 Correct 6 ms 29280 KB n=100
25 Correct 6 ms 29280 KB n=100
26 Correct 6 ms 29272 KB n=12
27 Correct 7 ms 29276 KB n=100
28 Correct 7 ms 29272 KB n=500
29 Correct 6 ms 29272 KB n=500
30 Correct 6 ms 29368 KB n=500
31 Correct 7 ms 29416 KB n=500
32 Correct 6 ms 29276 KB n=500
33 Correct 6 ms 29276 KB n=500
34 Correct 8 ms 29456 KB n=500
35 Correct 6 ms 29276 KB n=500
36 Correct 6 ms 29276 KB n=500
37 Correct 7 ms 29272 KB n=500
38 Correct 6 ms 29276 KB n=500
39 Correct 6 ms 29272 KB n=500
40 Correct 6 ms 29272 KB n=500
41 Correct 6 ms 29276 KB n=500
42 Correct 7 ms 29276 KB n=500
43 Correct 6 ms 29272 KB n=500
44 Correct 6 ms 29276 KB n=500
45 Correct 6 ms 29272 KB n=500
46 Correct 6 ms 29276 KB n=500
47 Correct 7 ms 29272 KB n=500
48 Correct 7 ms 29276 KB n=500
49 Correct 6 ms 29272 KB n=500
50 Correct 6 ms 29276 KB n=500
51 Correct 7 ms 29276 KB n=500
52 Correct 7 ms 29480 KB n=500
53 Correct 6 ms 29284 KB n=500
54 Correct 6 ms 29320 KB n=500
55 Correct 6 ms 29288 KB n=278
56 Correct 6 ms 29280 KB n=500
57 Correct 7 ms 29276 KB n=500
58 Correct 7 ms 29272 KB n=500
59 Correct 8 ms 29536 KB n=2000
60 Correct 9 ms 29708 KB n=2000
61 Correct 8 ms 29744 KB n=2000
62 Correct 8 ms 29532 KB n=2000
63 Correct 8 ms 29568 KB n=2000
64 Correct 10 ms 29536 KB n=2000
65 Correct 8 ms 29532 KB n=2000
66 Correct 8 ms 29532 KB n=2000
67 Correct 9 ms 29712 KB n=2000
68 Correct 8 ms 29556 KB n=2000
69 Correct 8 ms 29728 KB n=2000
70 Correct 8 ms 29528 KB n=2000
71 Correct 8 ms 29616 KB n=2000
72 Correct 8 ms 29528 KB n=2000
73 Correct 8 ms 29532 KB n=2000
74 Correct 8 ms 29528 KB n=1844
75 Correct 8 ms 29532 KB n=2000
76 Correct 8 ms 29532 KB n=2000
77 Correct 9 ms 29532 KB n=2000
78 Correct 8 ms 29532 KB n=2000
79 Correct 10 ms 29772 KB n=2000
80 Correct 8 ms 29528 KB n=2000
81 Correct 8 ms 29528 KB n=2000
82 Correct 9 ms 29532 KB n=2000
83 Correct 8 ms 29532 KB n=2000
84 Correct 8 ms 29528 KB n=2000
85 Correct 8 ms 29528 KB n=2000
86 Correct 8 ms 29532 KB n=2000
87 Correct 8 ms 29688 KB n=2000
88 Correct 8 ms 29788 KB n=2000
89 Correct 8 ms 29724 KB n=2000
90 Correct 8 ms 29784 KB n=2000
91 Correct 8 ms 29532 KB n=2000
92 Correct 567 ms 105068 KB n=200000
93 Correct 674 ms 109980 KB n=200000
94 Correct 466 ms 112956 KB n=200000
95 Correct 544 ms 104908 KB n=200000
96 Correct 525 ms 104884 KB n=200000
97 Correct 738 ms 109152 KB n=200000
98 Correct 556 ms 104952 KB n=200000
99 Correct 669 ms 105468 KB n=200000
100 Correct 573 ms 105188 KB n=200000
101 Correct 426 ms 113952 KB n=200000
102 Correct 313 ms 106436 KB n=200000
103 Correct 340 ms 106468 KB n=200000
104 Correct 331 ms 106680 KB n=200000
105 Correct 352 ms 106920 KB n=200000
106 Correct 322 ms 106828 KB n=200000
107 Correct 327 ms 106804 KB n=200000
108 Correct 570 ms 105300 KB n=200000
109 Correct 603 ms 105340 KB n=200000
110 Correct 582 ms 105100 KB n=200000
111 Correct 546 ms 104384 KB n=200000
112 Correct 445 ms 113232 KB n=200000
113 Correct 727 ms 109212 KB n=200000
114 Correct 594 ms 104720 KB n=200000
115 Correct 877 ms 107264 KB n=200000
116 Correct 561 ms 104948 KB n=200000
117 Correct 471 ms 113232 KB n=200000
118 Correct 863 ms 108628 KB n=200000
119 Correct 543 ms 105096 KB n=200000
120 Correct 349 ms 112684 KB n=200000
121 Correct 373 ms 112724 KB n=200000
122 Correct 382 ms 112976 KB n=200000
123 Correct 341 ms 106524 KB n=200000
124 Correct 115 ms 46232 KB n=25264