oj.uz

Submission #441975

# Submission time Handle Problem Language Result Execution time Memory
441975 2021-07-06T15:50:47 Z Nima_Naderi Birthday gift (IZhO18_treearray) C++14
100 / 100
 2349 ms 166704 KB 
//In the name of God
#include<bits/stdc++.h>
#define lc (id * 2)
#define rc (id * 2 + 1)
#define md ((s + e) / 2)
#define dm ((s + e) / 2 + 1)
#define ln (e - s + 1)
#define Mp make_pair
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> nima;
const ll MXN = 3e5 + 10;
const ll MXS = MXN * 4;
const ll LOG = 20;
ll n, m, q, timer;
ll Jad[LOG][MXN], dis[MXN];
ll Stm[MXN], Ftm[MXN], A[MXN], Arr[MXN];
vector<ll> adj[MXN];
multiset<nima> seg[MXS];
void prep(ll u, ll par){
	Stm[u] = ++ timer; Arr[timer] = u;
	Jad[0][u] = par;
	for(int i = 1; i < LOG; i ++){
		Jad[i][u] = Jad[i - 1][Jad[i - 1][u]];
	}
	for(auto v : adj[u]){
		if(v != par) dis[v] = dis[u] + 1, prep(v, u);
	}
	Ftm[u] = timer;
}
ll K_Jad(ll u, ll k){
	for(int i = 0; i < LOG; i ++){
		if((k >> i) & 1LL) u = Jad[i][u];
	}
	return u;
}
ll LCA(ll u, ll v){
	if(dis[u] > dis[v]) swap(u, v);
	v = K_Jad(v, dis[v] - dis[u]);
	if(u == v) return v;
	for(int i = LOG - 1; ~i; i --){
		if(Jad[i][u] != Jad[i][v]){
			u = Jad[i][u], v = Jad[i][v];
		}
	}
	return Jad[0][u];
}
bool Is_Jad(ll j, ll u){
	return Stm[j] <= Stm[u] && Ftm[u] <= Ftm[j];
}
void Ins(nima x, ll tp, ll p, ll id = 1, ll s = 1, ll e = m){
	if(tp)	seg[id].insert(x);
	else	seg[id].erase(seg[id].find(x));
	if(ln == 1) return;
	if(p <= md) Ins(x, p, lc, s, md);
	else 		Ins(x, p, rc, dm, e);
}
ll Get(ll l, ll r, ll stm, ll ftm, ll id = 1, ll s = 1, ll e = m){
	if(e < l || s > r) return -1;
	if(l <= s && e <= r){
		nima nw = Mp(Mp(stm, -1), -1);
		auto itr = seg[id].lower_bound(nw);
		if(itr == seg[id].end() || itr -> first.second > ftm) return -1;
		return itr -> second;
	}
	ll nw = Get(l, r, stm, ftm, lc, s, md);
	if(nw != -1) return nw;
	return Get(l, r, stm, ftm, rc, dm, e);
}
multiset<ll> my[MXN], sm[MXN];
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	assert(1LL << LOG > MXN);
	cin >> n >> m >> q;
	for(int i = 1; i < n; i ++){
		ll u, v; cin >> u >> v;
		adj[u].push_back(v), adj[v].push_back(u);
	}

	prep(1, 0);

	for(int i = 1, x; i <= m; i ++){
		cin >> x;
		nima now = Mp(Mp(Stm[x], Ftm[x]), i);
		//Ins(now, 1, i);
		A[i] = x;
        sm[x].insert(i);
	}
	for(int i = 2; i <= m; i ++){
		ll x = LCA(A[i - 1], A[i]);
		my[x].insert(i);
	}
	while(q --){
		ll t, x, y, z; cin >> t >> x >> y;
		if(t == 1){
			nima now = Mp(Mp(Stm[A[x]], Ftm[A[x]]), x);
			//Ins(now, 0, x);
			if(x + 1 <= m){
				ll xp = LCA(A[x], A[x + 1]);
				my[xp].erase(x + 1);
			}
			if(x - 1 >= 1){
				ll xp = LCA(A[x - 1], A[x]);
				my[xp].erase(x);
			}
			sm[A[x]].erase(x);
			A[x] = y;
			sm[A[x]].insert(x);
			now = Mp(Mp(Stm[A[x]], Ftm[A[x]]), x);
			//Ins(now, 1, x);
			if(x + 1 <= m){
				ll xp = LCA(A[x], A[x + 1]);
				my[xp].insert(x + 1);
			}
			if(x - 1 >= 1){
				ll xp = LCA(A[x - 1], A[x]);
				my[xp].insert(x);
			}
		} else {
			cin >> z; ll /*ans = Get(x, y, Stm[z], Ftm[z]);
			if(ans == -1){
				cout << -1 << ' ' << -1 << '\n';
				continue;
			}
			ll kid = A[ans];
			if(kid == z){
				cout << ans << ' ' << ans << '\n';
				continue;
			}*/
			ans = 1;
			if(sm[z].size()){
                auto itr = sm[z].lower_bound(x);
				if(itr != sm[z].end() && *itr <= y){
					cout << *itr << ' ' << *itr << '\n';
					ans = 0;
				}
			}
			if(ans && my[z].size()){
				auto itr = my[z].lower_bound(x + 1);
				if(itr != my[z].end() && *itr <= y){
                    if(LCA(A[*itr - 1], A[*itr]) == z){
                        cout << *itr - 1 << ' ' << *itr << '\n';
                        ans = 0;
                    }
                    else assert(0);
				}
			}
			if(ans) cout << -1 << ' ' << -1 << '\n';
		}
	}
	return 0;
}
// N.N

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:86:8: warning: variable 'now' set but not used [-Wunused-but-set-variable]
   86 |   nima now = Mp(Mp(Stm[x], Ftm[x]), i);
      |        ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 92084 KB n=5
2 Correct 59 ms 92096 KB n=100
3 Correct 59 ms 92020 KB n=100
4 Correct 62 ms 92108 KB n=100
5 Correct 57 ms 92064 KB n=100
6 Correct 59 ms 92044 KB n=100
7 Correct 66 ms 91996 KB n=100
8 Correct 59 ms 92100 KB n=100
9 Correct 58 ms 92020 KB n=100
10 Correct 57 ms 92068 KB n=100
11 Correct 58 ms 92064 KB n=100
12 Correct 61 ms 92064 KB n=100
13 Correct 58 ms 92112 KB n=100
14 Correct 59 ms 92112 KB n=100
15 Correct 59 ms 92040 KB n=100
16 Correct 58 ms 92084 KB n=100
17 Correct 59 ms 92100 KB n=100
18 Correct 62 ms 92100 KB n=100
19 Correct 57 ms 92112 KB n=100
20 Correct 59 ms 91988 KB n=100
21 Correct 58 ms 92108 KB n=100
22 Correct 57 ms 92052 KB n=100
23 Correct 56 ms 91992 KB n=100
24 Correct 58 ms 92100 KB n=100
25 Correct 57 ms 92128 KB n=100
26 Correct 58 ms 92084 KB n=12
27 Correct 63 ms 92116 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 92084 KB n=5
2 Correct 59 ms 92096 KB n=100
3 Correct 59 ms 92020 KB n=100
4 Correct 62 ms 92108 KB n=100
5 Correct 57 ms 92064 KB n=100
6 Correct 59 ms 92044 KB n=100
7 Correct 66 ms 91996 KB n=100
8 Correct 59 ms 92100 KB n=100
9 Correct 58 ms 92020 KB n=100
10 Correct 57 ms 92068 KB n=100
11 Correct 58 ms 92064 KB n=100
12 Correct 61 ms 92064 KB n=100
13 Correct 58 ms 92112 KB n=100
14 Correct 59 ms 92112 KB n=100
15 Correct 59 ms 92040 KB n=100
16 Correct 58 ms 92084 KB n=100
17 Correct 59 ms 92100 KB n=100
18 Correct 62 ms 92100 KB n=100
19 Correct 57 ms 92112 KB n=100
20 Correct 59 ms 91988 KB n=100
21 Correct 58 ms 92108 KB n=100
22 Correct 57 ms 92052 KB n=100
23 Correct 56 ms 91992 KB n=100
24 Correct 58 ms 92100 KB n=100
25 Correct 57 ms 92128 KB n=100
26 Correct 58 ms 92084 KB n=12
27 Correct 63 ms 92116 KB n=100
28 Correct 58 ms 92244 KB n=500
29 Correct 59 ms 92260 KB n=500
30 Correct 60 ms 92240 KB n=500
31 Correct 59 ms 92244 KB n=500
32 Correct 65 ms 92240 KB n=500
33 Correct 59 ms 92212 KB n=500
34 Correct 58 ms 92228 KB n=500
35 Correct 60 ms 92216 KB n=500
36 Correct 59 ms 92172 KB n=500
37 Correct 59 ms 92228 KB n=500
38 Correct 59 ms 92228 KB n=500
39 Correct 62 ms 92168 KB n=500
40 Correct 63 ms 92232 KB n=500
41 Correct 59 ms 92196 KB n=500
42 Correct 60 ms 92228 KB n=500
43 Correct 59 ms 92120 KB n=500
44 Correct 58 ms 92360 KB n=500
45 Correct 58 ms 92132 KB n=500
46 Correct 59 ms 92372 KB n=500
47 Correct 58 ms 92228 KB n=500
48 Correct 58 ms 92164 KB n=500
49 Correct 60 ms 92260 KB n=500
50 Correct 60 ms 92144 KB n=500
51 Correct 61 ms 92208 KB n=500
52 Correct 62 ms 92188 KB n=500
53 Correct 59 ms 92244 KB n=500
54 Correct 58 ms 92188 KB n=500
55 Correct 59 ms 92068 KB n=278
56 Correct 58 ms 92256 KB n=500
57 Correct 65 ms 92228 KB n=500
58 Correct 60 ms 92164 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 92084 KB n=5
2 Correct 59 ms 92096 KB n=100
3 Correct 59 ms 92020 KB n=100
4 Correct 62 ms 92108 KB n=100
5 Correct 57 ms 92064 KB n=100
6 Correct 59 ms 92044 KB n=100
7 Correct 66 ms 91996 KB n=100
8 Correct 59 ms 92100 KB n=100
9 Correct 58 ms 92020 KB n=100
10 Correct 57 ms 92068 KB n=100
11 Correct 58 ms 92064 KB n=100
12 Correct 61 ms 92064 KB n=100
13 Correct 58 ms 92112 KB n=100
14 Correct 59 ms 92112 KB n=100
15 Correct 59 ms 92040 KB n=100
16 Correct 58 ms 92084 KB n=100
17 Correct 59 ms 92100 KB n=100
18 Correct 62 ms 92100 KB n=100
19 Correct 57 ms 92112 KB n=100
20 Correct 59 ms 91988 KB n=100
21 Correct 58 ms 92108 KB n=100
22 Correct 57 ms 92052 KB n=100
23 Correct 56 ms 91992 KB n=100
24 Correct 58 ms 92100 KB n=100
25 Correct 57 ms 92128 KB n=100
26 Correct 58 ms 92084 KB n=12
27 Correct 63 ms 92116 KB n=100
28 Correct 58 ms 92244 KB n=500
29 Correct 59 ms 92260 KB n=500
30 Correct 60 ms 92240 KB n=500
31 Correct 59 ms 92244 KB n=500
32 Correct 65 ms 92240 KB n=500
33 Correct 59 ms 92212 KB n=500
34 Correct 58 ms 92228 KB n=500
35 Correct 60 ms 92216 KB n=500
36 Correct 59 ms 92172 KB n=500
37 Correct 59 ms 92228 KB n=500
38 Correct 59 ms 92228 KB n=500
39 Correct 62 ms 92168 KB n=500
40 Correct 63 ms 92232 KB n=500
41 Correct 59 ms 92196 KB n=500
42 Correct 60 ms 92228 KB n=500
43 Correct 59 ms 92120 KB n=500
44 Correct 58 ms 92360 KB n=500
45 Correct 58 ms 92132 KB n=500
46 Correct 59 ms 92372 KB n=500
47 Correct 58 ms 92228 KB n=500
48 Correct 58 ms 92164 KB n=500
49 Correct 60 ms 92260 KB n=500
50 Correct 60 ms 92144 KB n=500
51 Correct 61 ms 92208 KB n=500
52 Correct 62 ms 92188 KB n=500
53 Correct 59 ms 92244 KB n=500
54 Correct 58 ms 92188 KB n=500
55 Correct 59 ms 92068 KB n=278
56 Correct 58 ms 92256 KB n=500
57 Correct 65 ms 92228 KB n=500
58 Correct 60 ms 92164 KB n=500
59 Correct 62 ms 92644 KB n=2000
60 Correct 62 ms 92816 KB n=2000
61 Correct 62 ms 92784 KB n=2000
62 Correct 63 ms 92756 KB n=2000
63 Correct 65 ms 92740 KB n=2000
64 Correct 64 ms 92740 KB n=2000
65 Correct 66 ms 92740 KB n=2000
66 Correct 62 ms 92736 KB n=2000
67 Correct 69 ms 92736 KB n=2000
68 Correct 65 ms 92724 KB n=2000
69 Correct 61 ms 92724 KB n=2000
70 Correct 65 ms 92740 KB n=2000
71 Correct 62 ms 92740 KB n=2000
72 Correct 63 ms 92768 KB n=2000
73 Correct 61 ms 92640 KB n=2000
74 Correct 63 ms 92676 KB n=1844
75 Correct 60 ms 92680 KB n=2000
76 Correct 62 ms 92640 KB n=2000
77 Correct 64 ms 92760 KB n=2000
78 Correct 66 ms 92740 KB n=2000
79 Correct 72 ms 92664 KB n=2000
80 Correct 62 ms 92728 KB n=2000
81 Correct 61 ms 92716 KB n=2000
82 Correct 63 ms 92740 KB n=2000
83 Correct 70 ms 92732 KB n=2000
84 Correct 62 ms 92740 KB n=2000
85 Correct 62 ms 92652 KB n=2000
86 Correct 63 ms 92764 KB n=2000
87 Correct 63 ms 92740 KB n=2000
88 Correct 62 ms 92744 KB n=2000
89 Correct 65 ms 92828 KB n=2000
90 Correct 61 ms 92800 KB n=2000
91 Correct 62 ms 92664 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 92084 KB n=5
2 Correct 59 ms 92096 KB n=100
3 Correct 59 ms 92020 KB n=100
4 Correct 62 ms 92108 KB n=100
5 Correct 57 ms 92064 KB n=100
6 Correct 59 ms 92044 KB n=100
7 Correct 66 ms 91996 KB n=100
8 Correct 59 ms 92100 KB n=100
9 Correct 58 ms 92020 KB n=100
10 Correct 57 ms 92068 KB n=100
11 Correct 58 ms 92064 KB n=100
12 Correct 61 ms 92064 KB n=100
13 Correct 58 ms 92112 KB n=100
14 Correct 59 ms 92112 KB n=100
15 Correct 59 ms 92040 KB n=100
16 Correct 58 ms 92084 KB n=100
17 Correct 59 ms 92100 KB n=100
18 Correct 62 ms 92100 KB n=100
19 Correct 57 ms 92112 KB n=100
20 Correct 59 ms 91988 KB n=100
21 Correct 58 ms 92108 KB n=100
22 Correct 57 ms 92052 KB n=100
23 Correct 56 ms 91992 KB n=100
24 Correct 58 ms 92100 KB n=100
25 Correct 57 ms 92128 KB n=100
26 Correct 58 ms 92084 KB n=12
27 Correct 63 ms 92116 KB n=100
28 Correct 58 ms 92244 KB n=500
29 Correct 59 ms 92260 KB n=500
30 Correct 60 ms 92240 KB n=500
31 Correct 59 ms 92244 KB n=500
32 Correct 65 ms 92240 KB n=500
33 Correct 59 ms 92212 KB n=500
34 Correct 58 ms 92228 KB n=500
35 Correct 60 ms 92216 KB n=500
36 Correct 59 ms 92172 KB n=500
37 Correct 59 ms 92228 KB n=500
38 Correct 59 ms 92228 KB n=500
39 Correct 62 ms 92168 KB n=500
40 Correct 63 ms 92232 KB n=500
41 Correct 59 ms 92196 KB n=500
42 Correct 60 ms 92228 KB n=500
43 Correct 59 ms 92120 KB n=500
44 Correct 58 ms 92360 KB n=500
45 Correct 58 ms 92132 KB n=500
46 Correct 59 ms 92372 KB n=500
47 Correct 58 ms 92228 KB n=500
48 Correct 58 ms 92164 KB n=500
49 Correct 60 ms 92260 KB n=500
50 Correct 60 ms 92144 KB n=500
51 Correct 61 ms 92208 KB n=500
52 Correct 62 ms 92188 KB n=500
53 Correct 59 ms 92244 KB n=500
54 Correct 58 ms 92188 KB n=500
55 Correct 59 ms 92068 KB n=278
56 Correct 58 ms 92256 KB n=500
57 Correct 65 ms 92228 KB n=500
58 Correct 60 ms 92164 KB n=500
59 Correct 62 ms 92644 KB n=2000
60 Correct 62 ms 92816 KB n=2000
61 Correct 62 ms 92784 KB n=2000
62 Correct 63 ms 92756 KB n=2000
63 Correct 65 ms 92740 KB n=2000
64 Correct 64 ms 92740 KB n=2000
65 Correct 66 ms 92740 KB n=2000
66 Correct 62 ms 92736 KB n=2000
67 Correct 69 ms 92736 KB n=2000
68 Correct 65 ms 92724 KB n=2000
69 Correct 61 ms 92724 KB n=2000
70 Correct 65 ms 92740 KB n=2000
71 Correct 62 ms 92740 KB n=2000
72 Correct 63 ms 92768 KB n=2000
73 Correct 61 ms 92640 KB n=2000
74 Correct 63 ms 92676 KB n=1844
75 Correct 60 ms 92680 KB n=2000
76 Correct 62 ms 92640 KB n=2000
77 Correct 64 ms 92760 KB n=2000
78 Correct 66 ms 92740 KB n=2000
79 Correct 72 ms 92664 KB n=2000
80 Correct 62 ms 92728 KB n=2000
81 Correct 61 ms 92716 KB n=2000
82 Correct 63 ms 92740 KB n=2000
83 Correct 70 ms 92732 KB n=2000
84 Correct 62 ms 92740 KB n=2000
85 Correct 62 ms 92652 KB n=2000
86 Correct 63 ms 92764 KB n=2000
87 Correct 63 ms 92740 KB n=2000
88 Correct 62 ms 92744 KB n=2000
89 Correct 65 ms 92828 KB n=2000
90 Correct 61 ms 92800 KB n=2000
91 Correct 62 ms 92664 KB n=2000
92 Correct 2349 ms 159036 KB n=200000
93 Correct 1708 ms 162664 KB n=200000
94 Correct 1332 ms 165624 KB n=200000
95 Correct 2310 ms 158820 KB n=200000
96 Correct 1994 ms 158892 KB n=200000
97 Correct 1852 ms 161892 KB n=200000
98 Correct 2090 ms 158956 KB n=200000
99 Correct 2274 ms 158484 KB n=200000
100 Correct 2078 ms 159344 KB n=200000
101 Correct 1240 ms 166668 KB n=200000
102 Correct 1002 ms 159944 KB n=200000
103 Correct 956 ms 160048 KB n=200000
104 Correct 945 ms 160092 KB n=200000
105 Correct 952 ms 159860 KB n=200000
106 Correct 932 ms 159812 KB n=200000
107 Correct 956 ms 159812 KB n=200000
108 Correct 2090 ms 158944 KB n=200000
109 Correct 2041 ms 158716 KB n=200000
110 Correct 2098 ms 158720 KB n=200000
111 Correct 1807 ms 158844 KB n=200000
112 Correct 1291 ms 165932 KB n=200000
113 Correct 1852 ms 161728 KB n=200000
114 Correct 1769 ms 158728 KB n=200000
115 Correct 2182 ms 159976 KB n=200000
116 Correct 1928 ms 158672 KB n=200000
117 Correct 1277 ms 166100 KB n=200000
118 Correct 1932 ms 160700 KB n=200000
119 Correct 2019 ms 158592 KB n=200000
120 Correct 1194 ms 166128 KB n=200000
121 Correct 1183 ms 166084 KB n=200000
122 Correct 1219 ms 166704 KB n=200000
123 Correct 979 ms 159456 KB n=200000
124 Correct 319 ms 108216 KB n=25264