1859.md (21958B)
1 Source: https://codeforces.com/blog/entry/119287 2 3 We hope you liked the problems. 4 5 Task A was invented and prepared by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane"). 6 7 Task B was invented by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane"), and prepared by [artew](/profile/artew "Specialist artew"). 8 9 Task C was invented and prepared by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane"). 10 11 Task D was invented by [artew](/profile/artew "Specialist artew") and [efimovpaul](/profile/efimovpaul "Candidate Master efimovpaul"), and prepared by [artew](/profile/artew "Specialist artew"). 12 13 Task E was invented by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane") and [kristevalex](/profile/kristevalex "Grandmaster kristevalex"), and prepared by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane"). 14 15 Task F was invented by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane") and [Artyom123](/profile/Artyom123 "Grandmaster Artyom123"), and prepared by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane"). 16 17 [1859A - United We Stand](/contest/1859/problem/A "Codeforces Round 892 (Div. 2)") 18 19 **Hints** 20 21 **Hint 1** 22 23 What does it mean that $A$ divides $B$? 24 25 **Tutorial** 26 27 First, if all numbers are equal, then there is no answer (since $a$ is divisible by $a$, if both arrays are non-empty, then $c_1$ is a divisor of $b_1$). 28 29 Second, if $a$ is divisible by $b$ and they are both natural numbers, then the following equality holds: $b \le a$ (by definition, if $a$ is divisible by $b$, then $a$ can be represented as $k \dot b$, where $k$ is a natural number). 30 31 Now we can place all instances of the smallest number into $b$, and all other numbers into $c$. It can be seen that such a construction always gives a valid answer. 32 33 **Author's code** 34 35 ``` 36 #include <iostream> 37 #include <algorithm> 38 #include <vector> 39 using namespace std; 40 41 void solve() { 42 int n = 0; cin >> n; 43 vector<int> inp; inp.assign(n, 0); 44 for (auto& x : inp) cin >> x; 45 sort(inp.begin(), inp.end()); 46 if (inp.back() == inp[0]) { 47 cout << "-1\n"; 48 return; 49 } 50 else { 51 int it = 0; 52 while (inp[it] == inp[0]) it++; 53 cout << it << " " << n - it << "\n"; 54 for (int j = 0; j < it; ++j) cout << inp[j] << " "; 55 for (int j = it; j < n; ++j) cout << inp[j] << " "; 56 } 57 } 58 59 int main() { 60 int t = 0; cin >> t; 61 while (t--) solve(); 62 return 0; 63 } 64 ``` 65 66 [1859B - Olya and Game with Arrays](/contest/1859/problem/B "Codeforces Round 892 (Div. 2)") 67 68 **Hints** 69 70 **Hint 1** 71 72 Do all numbers in a single array really matter? 73 74 **Hint 2** 75 76 If only the first minimum and the second minimum matter, what is the only way to increase a single array's beauty? 77 78 **Hint 3** 79 80 What can we say about the array which will have the smallest number in the end? 81 82 **Tutorial** 83 84 To increase the answer for each array separately, it is necessary to move the minimum to another array. Then, notice that it is optimal to move all the minimums to one array. Let's figure out which array. After moving the minimum from an array, the second minimum in the original array becomes the new minimum. Then, it is easy to notice that it is optimal to move all the minimums to the array with the smallest second minimum. After all the movements, we will have one array where the minimum element is the smallest number among all the arrays, and $n-1$ arrays where the minimum element is the second minimum in the original array. 85 86 Therefore, the answer to the problem will be $M + K - S$, where $M$ is the minimum element among all the arrays, $K$ is the sum of all the second minimums, and $S$ is the smallest second minimum. 87 88 **Author's code** 89 90 ``` 91 #include <iostream> 92 #include <vector> 93 #include <algorithm> 94 #include <numeric> 95 96 using namespace std; 97 98 #define all(v) v.begin(), v.end() 99 100 typedef long long ll; 101 102 const int INF = 1e9 + 7; 103 104 void solve() { 105 int n; 106 cin >> n; 107 108 int minn = INF; 109 vector<int> min2; 110 for (int i = 0 ; i < n ; i++) { 111 int m; 112 cin >> m; 113 vector<int> v(m); 114 for (auto &el : v) cin >> el; 115 116 int minel = *min_element(all(v)); 117 minn = min(minn, minel); 118 v.erase(find(all(v), minel)); 119 min2.push_back(*min_element(all(v))); 120 } 121 cout << minn + (ll) accumulate(all(min2), 0ll) - *min_element(all(min2)) << "\n"; 122 } 123 124 signed main() { 125 ios_base::sync_with_stdio(0); 126 cin.tie(0); 127 128 #ifdef LOCAL 129 freopen("a.in", "r", stdin); 130 #endif 131 132 int t = 1; 133 cin >> t; 134 while (t--) 135 solve(); 136 137 return 0; 138 } 139 ``` 140 141 [1859C - Another Permutation Problem](/contest/1859/problem/C "Codeforces Round 892 (Div. 2)") 142 143 **Hints** 144 145 **Hint 1** 146 147 What if we fix the maximum element in the resulting array? 148 149 **Hint 2** 150 151 Try using greedy. 152 153 **Hint 3** 154 155 Optimize the log factor away by noticing a certain fact. 156 157 **Tutorial** 158 159 Let's fix the maximum element in an array — let it be $M$. Now, let's iterate from $n$ to $1$. Let the current chosen number be $i$. I claim that if we maintain the remaining available numbers to multiply by, then it is optimal to take the maximum such number $x$ that $x * i \le M$. 160 161 Proof: let's say that this is not correct. Then, let's say that we pair $i$ with another number $x1$, and $x$ gets paired with some other number $i1$. Then, $i1 \lt i$, because it was chosen later, and $x1 \lt x$ (otherwise $i * x1 \gt M$). Now let's swap $x$ with $x1$. The sum is increased by $i * x - i * x1 - i1 * x + i1 * x1 = (i - i1)(x - x1) \gt 0$, and all of the numbers are less or equal to $M$. 162 163 Now the task can be solved in $O(N^3logN)$ by simply iterating on the maximum from $N^2$ to $1$, while maintaining the remaining numbers with a set. In order to squeeze it in the TL, you can only consider such maximums that they can be represented as $i * j, 1 \le i, j \le n$. 164 165 In order to optimize it to $O(N^3)$, let's notice that for each number $x$, it can be paired with any number from $1$ to $\frac{M} {x}$. Now just maintain a stack of all available elements at the current moment, add all numbers that possible, and pop the maximum number for all $i$ from $1$ to $N$. 166 167 **Author's code** 168 169 ``` 170 #include <iostream> 171 #include <algorithm> 172 #include <set> 173 #include <stack> 174 #include <vector> 175 using namespace std; 176 void solve() { 177 int N = 0; cin >> N; 178 int ans = 0; 179 vector<int> pr; 180 pr.assign(N * N, -1); 181 for (int i = 1; i <= N; ++i) { 182 for (int j = 1; j <= N; ++j) { 183 pr[i * j - 1] = 1; 184 } 185 } 186 for (int mx = N * N; mx >= 1; --mx) { 187 if (pr[mx - 1] == -1) continue; 188 vector<vector<int>> a; 189 int curans = -mx; 190 bool br = false; 191 a.assign(N, vector<int>()); 192 for (int j = N; j >= 1; --j) { 193 int num = min(mx / j, N); 194 if (num < 1) { 195 br = true; 196 break; 197 } 198 a[num - 1].push_back(j); 199 } 200 if (br) break; 201 stack<int> s; 202 for (int i = 0; i < N; ++i) { 203 s.push(i + 1); 204 bool brk = false; 205 for (auto x : a[i]) { 206 if (s.empty()) { 207 brk = true; break; 208 } 209 curans += s.top() * x; 210 s.pop(); 211 } 212 if (brk) break; 213 } 214 ans = max(ans, curans); 215 } 216 cout << ans << "\n"; 217 } 218 219 int main() { 220 ios_base::sync_with_stdio(false); 221 cin.tie(nullptr); 222 int t = 0; cin >> t; 223 while (t--) solve(); 224 return 0; 225 } 226 ``` 227 228 [1859D - Andrey and Escape from Capygrad](/contest/1859/problem/D "Codeforces Round 892 (Div. 2)") 229 230 **Hints** 231 232 **Hint 1** 233 234 What if we use greedy a bit? 235 236 **Hint 2** 237 238 Where it is always beneficial to teleport? 239 240 **Hint 3** 241 242 Use scanline 243 244 **Tutorial** 245 246 Statement: It is always beneficial to teleport to point $b_i$. 247 248 Proof: Let's assume that we were able to teleport from point $X$ to the right of $b_i$, but not from $b_i$. Then we used some segment $A$ that covers point $X$, but does not cover point $b$, and ends to the right of $b$. This is a contradiction. 249 250 Let $ans_i$ be the maximum coordinate we can reach while being on segment $i$, and let $p_j$ be the answer to the $j$-th query. Then we notice that the answer to query $p_j = \max(x_j, \max_{i = 1}^n {ans_i \vert l_i \le x_j \le r_i})$. 251 252 We will use the scanline method from the end. Events: $l_i$, $b_i$, $r_i$, $x_j$. 253 254 We notice that events of type $r_i$ are not important to us when scanning from the end (according to statement number 1). It is important for us that we process events of type $b_i$ first, then events of type $x_j$, and then events of type $l_i$ (closing the segment in the scanline). 255 256 We will go through the events of the scanline, processing them in the order of $b_i$, then events of type $x_j$, and then events of type $l_i$. 257 258 We assume that there is a data structure that allows us to add elements, remove elements, and quickly output the maximum. 259 260 * For each event of type $b_i$, update the value of $ans_i$ — take the maximum value of $ans$ of all open segments from the structure. 261 * For each event of type $x_j$, update the value of $p_j$ — take the maximum value of $ans$ of all open segments from the structure, as well as $x_j$. 262 * For each event of type $l_i$, remove $ans_i$ from the structure. 263 264 We notice that to solve this problem, we can use the std::multiset} container, which automatically sorts elements in ascending order. We can store in $multiset$ $ans_i$ of all open segments. And then, when processing events, extract the maximum from $multiset$, all operations are performed in $O(\log n)$. This allows us to solve the problem in $O((n + q) \log n)$ time and $O(n)$ memory. 265 266 **Author's code** 267 268 ``` 269 #include <iostream> 270 #include <vector> 271 #include <set> 272 #include <iomanip> 273 #include <cmath> 274 #include <algorithm> 275 #include <map> 276 #include <stack> 277 #include <cassert> 278 #include <unordered_map> 279 #include <bitset> 280 #include <random> 281 #include <unordered_set> 282 #include <chrono> 283 284 using namespace std; 285 286 #define all(a) a.begin(), a.end() 287 288 void solve() { 289 int n; 290 cin >> n; 291 292 vector<int> ans(n); 293 vector<tuple<int, int, int>> events; 294 for (int i = 0 ; i < n ; i++) { 295 int l, r, a, b; 296 cin >> l >> r >> a >> b; 297 ans[i] = b; 298 events.emplace_back(b, 1, i); 299 events.emplace_back(l, -1, i); 300 } 301 int q; 302 cin >> q; 303 vector<int> queries(q); 304 for (int i = 0 ; i < q ; i++) { 305 int x; 306 cin >> x; 307 queries[i] = x; 308 events.emplace_back(x, 0, i); 309 } 310 311 sort(all(events)); 312 reverse(all(events)); 313 multiset<int> s; 314 for (auto [x, type, ind] : events) { 315 if (type == 1) { 316 if (!s.empty()) { 317 ans[ind] = *s.rbegin(); 318 } 319 s.insert(ans[ind]); 320 } else if (type == 0) { 321 if (!s.empty()) { 322 queries[ind] = max(queries[ind], *s.rbegin()); 323 } 324 } else { 325 s.extract(ans[ind]); 326 } 327 } 328 329 for (auto el : queries) 330 cout << el << " "; 331 cout << "\n"; 332 } 333 334 signed main() { 335 ios_base::sync_with_stdio(false); 336 cin.tie(nullptr); 337 338 int t = 1; 339 cin >> t; 340 while (t--) 341 solve(); 342 343 return 0; 344 } 345 ``` 346 347 [1859E - Maximum Monogonosity](/contest/1859/problem/E "Codeforces Round 892 (Div. 2)") 348 349 **Hints** 350 351 **Hint 1** 352 353 Maybe we can relax some conditions? 354 355 **Hint 2** 356 357 Do we really need to always correctly calculate all sums? 358 359 **Hint 3** 360 361 Optimize the obvious dp. 362 363 **Tutorial** 364 365 Let's call the value of a segment $[l; r]$ $f(l, r) = abs(a_l - b_r) + abs(a_r - b_l)$. 366 367 Let's write $dp[n1][k1]$ — maximum value of segments of total length $k1$ that end before $n1$. 368 369 The obvious way to recalc is the following: 370 371 $dp[n1][k1] = max(dp[n1 - 1][k1], dp[n1 - l][k1 - l] + f(n1 - l + 1, n1), 1 \le l \le k1)$. 372 373 This works in $O(NK^2)$ and is too slow. 374 375 Now let's consider the following: instead of getting the absolute value of segment $[l; r]$, we consider the maximum of the following four combinations: $b_l - a_r + b_r - a_l$, $b_l - a_r - b_r + a_l$, $-b_l + a_r + b_r - a_l$, $-b_l + a_r - b_r + a_l$. We can see that this always gives us the correct answer to the absolute value, since we check all of the possibilities. 376 377 Now we can look at out dp states as a table, and notice that we recalc over the diagonal (we recalc over all states that have the same value of n1 — k1). 378 379 Now, for each "diagonal", we maintain four maximum combinations: $dp[n1][k1] + b_{k1} + a_{k1}, dp[n1][k1] - b_{k1} + a_{k1}, dp[n1][k1] + b_{k1} - a_{k1}, dp[n1][k1] - b_{k1} - a_{k1}$, and when we want to recalc state $dp[n2][k2]$, we just consider all of the four possibilities. 380 381 **Author's code** 382 383 ``` 384 #include <iostream> 385 #include <vector> 386 using namespace std; 387 const long long INF = 1e18; 388 #define int long long 389 390 void solve() { 391 int N = 0, K = 0; cin >> N >> K; 392 vector<int> a; 393 vector<int> b; 394 a.assign(N, 0); 395 b.assign(N, 0); 396 for (int i = 0; i < N; ++i) { 397 cin >> a[i]; 398 } 399 for (int i = 0; i < N; ++i) { 400 cin >> b[i]; 401 } 402 vector<long long> mx1; // max of (b_l + a_l) + corresponding dp 403 vector<long long> mx2; // max of (b_l - a_l) + corresponding dp 404 vector<long long> mn1; // min of (b_l + a_l) + corresponding dp 405 vector<long long> mn2; // min of (b_l - a_l) + corresponding dp 406 vector<vector<long long>> dp; 407 mx1.assign(N + 1, -INF); mx2.assign(N + 1, -INF); 408 mn1.assign(N + 1, INF); mn2.assign(N + 1, INF); 409 dp.assign(N + 1, vector<long long>(K + 1, 0)); 410 for (int i = 0; i <= N; ++i) { 411 for (int j = 0; j <= min(i, K); ++j) { 412 if (i != 0) dp[i][j] = dp[i - 1][j]; 413 int diag_val = i - j; 414 if (i != 0) { 415 dp[i][j] = max(dp[i][j], b[i - 1] + a[i - 1] - mn1[diag_val]); 416 dp[i][j] = max(dp[i][j], -b[i - 1] - a[i - 1] + mx1[diag_val]); 417 dp[i][j] = max(dp[i][j], a[i - 1] - b[i - 1] - mn2[diag_val]); 418 dp[i][j] = max(dp[i][j], b[i - 1] - a[i - 1] + mx2[diag_val]); 419 } 420 if (i != N) { 421 mn1[diag_val] = min(mn1[diag_val], b[i] + a[i] - dp[i][j]); 422 mx1[diag_val] = max(mx1[diag_val], b[i] + a[i] + dp[i][j]); 423 mn2[diag_val] = min(mn2[diag_val], b[i] - a[i] - dp[i][j]); 424 mx2[diag_val] = max(mx2[diag_val], b[i] - a[i] + dp[i][j]); 425 } 426 } 427 } 428 cout << dp[N][K] << "\n"; 429 } 430 431 432 signed main() { 433 int T = 1; 434 cin >> T; 435 while (T--) { 436 solve(); 437 } 438 } 439 ``` 440 441 [1859F - Teleportation in Byteland](/contest/1859/problem/F "Codeforces Round 892 (Div. 2)") 442 443 **Hints** 444 445 **Hint 1** 446 447 How many times do we really need to take driving courses? 448 449 **Hint 2** 450 451 Can you think how would an optimal answer path look like? 452 453 **Hint 3** 454 455 Can you recalculate the distances required to get to a city from every vertex? 456 457 **Tutorial** 458 459 Root the tree arbitrarily. 460 461 First, we can notice that there is no need to take driving courses more than $log{maxW}$ times. 462 463 Now, let's iterate for the number of driving courses we take from $0$ to $20$ ($2^{20} \gt 1000000$). For each number we solve separately. 464 465 Let us fix the number of taken as $q$. Now the path looks like the following: we go over the simple path, then we veer off to take courses in some town, then we come back to the path and finish it. Let's call $d[x]$ the minimum distance required to get from $x$ to a town which offers driving courses and then come back to the same town. We can recalculate $d[x]$ with multi-source BFS. 466 467 Now, let's look at the vertex $v1$ on the path, from which we will start going off the path. Then, the cost of the path is $d[v1]$ + distance from $a$ to $v1$ on the original edges (with $c = 1$) + distance from $v1$ to $b$ on the modified edges(with $c = 2^{q}$). 468 469 Now let's look at some cases, let $LCA$ be the LCA of $a$ and $b$, $h1[x]$ — the sum of all original edges from the root downwards to $x$, $h2[x]$ — the sum of all modified edges from the root downwards to $x$. 470 471 If $v1$ is between $LCA$ and $a$, the cost is $h1[a] - h1[v1] + d1[v1] - h2[LCA] + h2[v1] + h2[b] - h2[LCA]$. If $v1$ is between $LCA$ and $a$, the cost is $h1[a] - h1[LCA] + h1[v1] - h1[LCA] + d1[v1] + h2[b] - h2[v1]$. Now we simply need to consider the terms which depend only on $v1$, and then we need to take the maximum value on a path. For that we can use binary lifting, and for LCA as well. 472 473 **Author's code** 474 475 ``` 476 #include <iostream> 477 #include <iomanip> 478 #include <fstream> 479 #include <vector> 480 #include <numeric> 481 #include <algorithm> 482 #include <set> 483 #include <map> 484 #include <cmath> 485 #include <stack> 486 #include <deque> 487 #include <string> 488 #include <ctime> 489 #include <bitset> 490 #include <queue> 491 #include <cassert> 492 #include<unordered_set> 493 #include<unordered_map> 494 #include<string.h> 495 #include <random> 496 #include <chrono> 497 #include <math.h> 498 using namespace std; 499 #define pi pair<int, int> 500 #define ll long long 501 #define pll pair<ll, ll> 502 const ll INF = 1e18; 503 vector<vector<pi>> g; 504 vector<int> is_special; 505 vector<vector<int>> bin_lift; 506 vector<vector<pi>> new_g; 507 vector<int> tin; 508 vector<int> tout; 509 vector<ll> ans; 510 vector<pi> req; 511 vector<ll> h_orig; 512 vector<ll> h_new; 513 vector<ll> d; 514 vector<bool> used_bfs; 515 vector<vector<pll>> bin_lift_2; 516 vector<int> lc; 517 vector<int> top_order; 518 vector<pair<int, int>> pr; 519 int TIMER = 0; 520 void DFS(int v, int p) { 521 top_order.push_back(v); 522 tin[v] = TIMER++; 523 bin_lift[v][0] = p; 524 for (int i = 1; i < 17; ++i) { 525 if (bin_lift[v][i - 1] == -1) break; 526 bin_lift[v][i] = bin_lift[bin_lift[v][i - 1]][i - 1]; 527 } 528 for (auto& x : g[v]) { 529 if (x.first == p) { 530 pr.push_back(x); 531 continue; 532 } 533 } 534 for (auto& x : g[v]) { 535 if (x.first == p) continue; 536 h_orig[x.first] = h_orig[v] + x.second; 537 DFS(x.first, v); 538 } 539 tout[v] = TIMER; 540 } 541 void BFS(int N) { 542 priority_queue<pll> q; 543 for (int i = 0; i < N; ++i) { 544 if (is_special[i]) { 545 q.push({ -0, i }); 546 d[i] = 0; 547 } 548 } 549 while (!q.empty()) { 550 int v = q.top().second; q.pop(); 551 if (used_bfs[v]) continue; 552 used_bfs[v] = true; 553 for (auto& x : new_g[v]) { 554 if (d[x.first] > d[v] + x.second) { 555 d[x.first] = d[v] + x.second; 556 q.push({ -d[x.first], x.first }); 557 } 558 } 559 } 560 } 561 inline bool isIn(int a, int b) { 562 return tin[a] <= tin[b] && tout[a] >= tout[b]; 563 } 564 int gLCA(int a, int b) { 565 if (isIn(a, b)) return a; 566 if (isIn(b, a)) return b; 567 int cB = b; 568 for (int i = 16; i >= 0; --i) { 569 if (bin_lift[cB][i] == -1) continue; 570 if (!isIn(bin_lift[cB][i], a)) cB = bin_lift[cB][i]; 571 } 572 return bin_lift[cB][0]; 573 } 574 ll g1(int a, int LCA) { 575 ll mn = d[a] + h_new[a] - h_orig[a]; 576 int cK = a; 577 for (int i = 16; i >= 0; --i) { 578 if (bin_lift[cK][i] == -1) continue; 579 if (!isIn(LCA, bin_lift[cK][i])) continue; 580 mn = min(mn, bin_lift_2[cK][i].first); 581 cK = bin_lift[cK][i]; 582 } 583 return mn; 584 } 585 ll g2(int a, int LCA) { 586 ll mn = d[a] + h_orig[a] - h_new[a]; 587 int cK = a; 588 for (int i = 16; i >= 0; --i) { 589 if (bin_lift[cK][i] == -1) continue; 590 if (!isIn(LCA, bin_lift[cK][i])) continue; 591 mn = min(mn, bin_lift_2[cK][i].second); 592 cK = bin_lift[cK][i]; 593 } 594 return mn; 595 } 596 void solve() { 597 top_order.clear(); 598 pr.clear(); 599 int N = 0, T = 0; cin >> N >> T; 600 g.assign(N, vector<pi>()); 601 for (int j = 0; j < N - 1; ++j) { 602 int u = 0, v = 0, w = 0; cin >> u >> v >> w; 603 u--; v--; 604 g[u].push_back({ v, w }); g[v].push_back({ u, w }); 605 } 606 is_special.assign(N, 0); 607 string s = ""; cin >> s; 608 for (int i = 0; i < N; ++i) is_special[i] = s[i] - '0'; 609 tin.assign(N, 0); tout.assign(N, 0); 610 bin_lift.assign(N, vector<int>(17, -1)); 611 TIMER = 0; 612 h_orig.assign(N, 0); 613 DFS(0, -1); 614 int Q = 0; cin >> Q; 615 ans.assign(Q, INF); 616 req.clear(); 617 lc.clear(); 618 for (int j = 0; j < Q; ++j) { 619 int u = 0, v = 0; cin >> u >> v; 620 u--; v--; 621 req.push_back({ u, v }); 622 lc.push_back(gLCA(u, v)); 623 } 624 bin_lift_2.assign(N, vector<pll>(17, pll(INF, INF))); 625 h_new.assign(N, 0); 626 for (ll level = 1; level <= 20; ++level) { 627 const int w = (1ll << level); 628 new_g.assign(N, vector<pi>()); 629 for (int i = 0; i < N; ++i) { 630 for (int j = 0; j < g[i].size(); ++j) { 631 new_g[i].push_back({ g[i][j].first, g[i][j].second + ((g[i][j].second + w - 1) / w) }); 632 } 633 } 634 d.assign(N, INF); 635 used_bfs.assign(N, false); 636 BFS(N); 637 h_new[0] = 0; 638 for (int n = 1; n < N; ++n) { 639 h_new[top_order[n]] = h_new[pr[n - 1].first] + (pr[n - 1].second + w - 1) / w; 640 int p = pr[n - 1].first; 641 int v = top_order[n]; 642 bin_lift_2[v][0] = { d[p] + h_new[p] - h_orig[p], d[p] + h_orig[p] - h_new[p] }; 643 for (int i = 1; i < 17; ++i) { 644 if (bin_lift[v][i] == -1) break; 645 bin_lift_2[v][i].first = min(bin_lift_2[v][i - 1].first, bin_lift_2[bin_lift[v][i - 1]][i - 1].first); 646 bin_lift_2[v][i].second = min(bin_lift_2[v][i - 1].second, bin_lift_2[bin_lift[v][i - 1]][i - 1].second); 647 } 648 } 649 for (int j = 0; j < Q; ++j) { 650 int a1 = req[j].first; int b1 = req[j].second; 651 int LCA = lc[j]; 652 ans[j] = min(ans[j], g1(a1, LCA) + h_orig[a1] - h_new[LCA] + h_new[b1] - h_new[LCA] + level * T); 653 ans[j] = min(ans[j], g2(b1, LCA) + h_orig[a1] - h_orig[LCA] - h_orig[LCA] + h_new[b1] + level * T); 654 } 655 } 656 for (int i = 0; i < Q; ++i) { 657 ans[i] = min(ans[i], h_orig[req[i].first] + h_orig[req[i].second] - 2 * h_orig[lc[i]]); 658 cout << ans[i] << "\n"; 659 } 660 } 661 662 signed main() { 663 ios_base::sync_with_stdio(false); 664 cin.tie(0); 665 cout.tie(0); 666 cout << setprecision(12); 667 int T = 1; 668 cin >> T; 669 while (T--) { 670 solve(); 671 } 672 return 0; 673 } 674 ``` 675 676 Some notes/challenges: 677 678 * We know about the $O(N^2)$ solution in C, but we did not find a good suitable proof for it (and, using the method, we could achieve faster solutions). 679 * You can solve $D$ without the constraint that the segments are contained, but that is harder. It is solvable in $(ONlogN)$. 680 * Thank you all for participating! If you have any complaints/suggestions/advice for future rounds, feel free to share in the comments!