1801.md (35376B)
1 Source: https://codeforces.com/blog/entry/113857 2 3 ## [1802A - Likes](/contest/1802/problem/A "Codeforces Round 857 (Div. 2)") 4 5 Idea: [Aleks5d](/profile/Aleks5d "International Master Aleks5d"), Preparation: [vaaven](/profile/vaaven "Master vaaven") 6 7 **Solution** 8 9 Let's show a construction that maximizes the number of likes. We need to first leave all the likes that we can put, and only then delete them. 10 11 To minimize the number of likes, we need to delete the like (if we can) immediately after we post it. 12 13 The code below implements these constructs. 14 15 **Code** 16 17 ``` 18 #include "bits/stdc++.h" 19 20 using namespace std; 21 22 void solve() { 23 int n; 24 cin >> n; 25 int likes = 0, dislikes = 0; 26 for (int i = 0; i < n; i++) { 27 int x; 28 cin >> x; 29 if (x > 0) likes++; 30 else dislikes++; 31 } 32 for (int i = 1; i <= n; ++i) { 33 if (i <= likes) cout << i << ' '; 34 else cout << likes * 2 - i << ' '; 35 } 36 cout << '\n'; 37 38 for (int i = 1; i <= n; ++i) { 39 if (i <= dislikes * 2) cout << i % 2 << ' '; 40 else cout << (i - dislikes * 2) << ' '; 41 } 42 cout << '\n'; 43 } 44 45 signed main() { 46 int t = 1; 47 cin >> t; 48 for (int i = 1; i <= t; ++i) { 49 solve(); 50 } 51 return 0; 52 } 53 ``` 54 55 ## [1802B - Settlement of Guinea Pigs](/contest/1802/problem/B "Codeforces Round 857 (Div. 2)") 56 57 Idea and preparation: [Aleks5d](/profile/Aleks5d "International Master Aleks5d") 58 59 **Solution** 60 61 Todo 62 63 **Code** 64 65 ``` 66 #include<bits/stdc++.h> 67 68 using namespace std; 69 70 void solve() { 71 int n; 72 cin >> n; 73 int known = 0, unknown = 0; 74 int need = 0; 75 for (int i = 0; i < n; ++i) { 76 int x; 77 cin >> x; 78 if (x == 1) ++unknown; 79 else { 80 known += unknown; 81 unknown = 0; 82 } 83 need = max(need, unknown + (known ? known / 2 + 1 : 0)); 84 } 85 cout << need << endl; 86 } 87 88 signed main() { 89 int t = 1; 90 cin >> t; 91 for (int i = 0; i < t; ++i) { 92 solve(); 93 } 94 return 0; 95 } 96 ``` 97 98 ## [1801A - The Very Beautiful Blanket](/contest/1801/problem/A "Codeforces Round 857 (Div. 1)") 99 100 Idea and preparation: [4qqqq](/profile/4qqqq "Expert 4qqqq") 101 102 **Solution** 103 104 The maximum number of different numbers we can type is always $n\cdot m$. Let's show how you can build an example for any $n$ and $m$. 105 106 Note that if we were able to construct a correct matrix, then any of its submatrix is also a correct matrix of a smaller size. Therefore, let's build a correct matrix for some $N$ and $M$, and as an answer we will output the upper left corner of this matrix of the desired size. 107 108 Take $N = M = 2^8$ and construct the matrix using the following algorithm. Let's break it into blocks of size $2 \times 2$. Let's number the blocks from left to right and from top to bottom in order, starting from zero. The $i$th block will have the form 109 110 $4i + 0$ $4i + 1$ 111 112 $4i + 2$ $4i + 3$ 113 114 With this construction, the bitwise exclusive OR any submatrix of size $2\times 2$ will be zero. You can verify this as follows. Let's look at the upper left corner of $(i,\,j)$ of an arbitrary submatrix of size $2\times 2$. There are 4 cases: 115 116 1. both coordinates are even; 117 2. $i$ is even, $j$ is odd; 118 3. $i$ odd, $j$ even; 119 4. both coordinates are odd. 120 121 Immediately note that $i, \, j \lt 200 \lt 2^8$ 122 123 Consider the most unpleasant case — the last one. The remaining cases are treated in a similar way. In this case, the submatrix will have the form: 124 125 $4i + 3$ $4(i + 1) + 2$ 126 127 $4(i + 2^8) + 1$ $4(i + 2^8 + 1) + 0$ 128 129 Note that the second part of each term is less than 4, and the first part of each term is greater than or equal to 4. Therefore, they can be considered independently. 130 131 $3 \oplus 2 \oplus 1 \oplus 0$ $=$ $0$. 132 133 If $i$$=$$1$, then 134 135 $4i \oplus 4(i + 1)$ $=$ $12$, 136 137 $4(1 + 2^8) \oplus 4(2 + 2^8)$ $=$ $12$. 138 139 If $i\neq 1$, then 140 141 $4i \oplus 4(i + 1)$ $=$ $4$ 142 143 $4(i + 2^8) \oplus 4(i + 2^8 + 1)$$=$$4$ (for $i=0$, you can check with your hands, for $1 \lt i \lt 2^8$ $4(i+ 2^8)$ will be reduced and $4$ will remain from the second term). 144 145 $4 \oplus 4 \oplus 0$ $=$ $0$. Thus, in the selected submatrix, the bitwise exclusive OR is zero. 146 147 **Code** 148 149 ``` 150 #include <bits/stdc++.h> 151 152 using namespace std; 153 154 typedef long long ll; 155 156 const int SZ = 256; 157 158 int v[SZ][SZ]; 159 160 void Solve(){ 161 int n, m; 162 cin >> n >> m; 163 164 cout << n * m << '\n'; 165 166 for(int i = 0; i < n; i++) 167 for(int j = 0; j < m; j++) 168 cout << v[i][j] << " \n"[j + 1 == m]; 169 } 170 171 signed main(){ 172 ios_base::sync_with_stdio(NULL); 173 cin.tie(NULL); 174 cout.tie(NULL); 175 176 { 177 int now = 0; 178 int n = 256; 179 int m = 256; 180 181 for(int i = 0; i < n; i += 2) 182 for(int j = 0; j < m; j += 2){ 183 v[i][j] = now; 184 v[i][j + 1] = now + 1; 185 v[i + 1][j] = now + 2; 186 v[i + 1][j + 1] = now + 3; 187 now += 4; 188 } 189 } 190 191 int num_test = 1; 192 cin >> num_test; 193 194 for(int i = 1; i <= num_test; i++){ 195 Solve(); 196 } 197 } 198 ``` 199 200 ## [1801B - Buying gifts](/contest/1801/problem/B "Codeforces Round 857 (Div. 1)") 201 202 Idea: [Tikhon228](/profile/Tikhon228 "Master Tikhon228"), Preparation: [DishonoredRighteous](/profile/DishonoredRighteous "Grandmaster DishonoredRighteous") 203 204 **Solution** 205 206 To begin with, let's sort all departments in descending order $b_i$ (and if ~--- is equal, in ascending order $a_i$). Now let's go through the $i$ department, in which the most expensive gift for the second girlfriend will be bought. Note that in all departments with numbers $j \lt i$, Sasha must buy a gift for the first girlfriend, otherwise the gift $i$ will not have the maximum value among the gifts bought for the second girlfriend. Therefore, we will immediately find the value of $m = \max \limits_{j \lt i} a_j$. Thus, we can already get the answer $\lvert m - b_i\rvert$. 207 208 In all departments with numbers $j \gt i$, for which $a_j \le m$, Sasha can buy a gift for any of her friends, and this will not affect the answer in any way. Now consider all departments with numbers $j \gt i$ for which $a_j \gt m$. If you buy a gift for your first girlfriend in some of these departments, the value of $m$ will increase, which means the answer may improve. Therefore, let's iterate through all these departments and update the response with the value $\lvert a_j - b_i\rvert$. 209 210 Time $O(n^2)$. 211 212 Let's optimize this solution. To begin with, instead of calculating the value of $m$ anew at each iteration, we will maintain its value in some variable. Then, when moving from department $i - 1$ to department $i$, we will update the value of $m$ as follows: $m:= \max(m, a_i)$. 213 214 It remains to learn how to quickly find the optimal department number $j$, such that $j \gt i$, $a_j \gt m$, as well as $\lvert a_j - b_i\rvert$ is minimal. Let's choose on the suffix of the array the minimum $a_j$, such that $a_j\ge b_i$, and also the maximum $a_j$, such that $a_j \le b_i$. You can notice that the optimal $a_j$ is one of the two selected numbers (you also need to remember to check the condition $a_j \gt m$). Therefore, it is enough to update the answer only with the help of them. 215 216 You can search for these two elements using the \texttt{set} data structure. We will support in the set all $a_j$ located on the suffix. Then you can find the necessary two elements for $O(\log n)$. When moving from department $i - 1$ to department $i$, you need to remove the value $a_{i - 1}$ from the data structure. 217 218 Time $O(n\log n)$ 219 220 **Code** 221 222 ``` 223 #include <bits/stdc++.h> 224 225 using namespace std; 226 227 template<typename T> 228 bool smin(T& a, const T& b) { 229 if (b < a) { 230 a = b; 231 return true; 232 } 233 return false; 234 } 235 236 template<typename T> 237 bool smax(T& a, const T& b) { 238 if (a < b) { 239 a = b; 240 return true; 241 } 242 return false; 243 } 244 245 const int INF = 0x3f3f3f3f; 246 const int N = 500100; 247 248 std::pair<int, int> a[N]; 249 250 void run() { 251 int n; 252 scanf("%d", &n); 253 254 for (int i = 0; i < n; ++i) { 255 scanf("%d%d", &a[i].first, &a[i].second); 256 } 257 258 sort(a, a + n, [&](const pair<int, int>& p1, 259 const pair<int, int>& p2) { 260 return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first); 261 }); 262 263 multiset<int> setik; 264 for (int i = 0; i < n; ++i) { 265 setik.insert(a[i].first); 266 } 267 268 int mx = -INF; 269 int ans = INF; 270 271 for (int i = 1; i < n; ++i) { 272 smin(ans, abs(a[i].first - a[0].second)); 273 } 274 275 for (int i = 0; i < n; ++i) { 276 setik.erase(setik.find(a[i].first)); 277 if (i == 0) { 278 mx = a[i].first; 279 continue; 280 } 281 282 smin(ans, abs(mx - a[i].second)); 283 auto it = setik.lower_bound(a[i].second); 284 if (it != setik.end() && *it >= mx) { 285 smin(ans, abs(*it - a[i].second)); 286 } 287 if (it != setik.begin() && *std::prev(it) >= mx) { 288 smin(ans, abs(*prev(it) - a[i].second)); 289 } 290 291 smax(mx, a[i].first); 292 } 293 294 printf("%d\n", ans); 295 } 296 297 int main(void) { 298 int t; 299 scanf("%d", &t); 300 while (t--) { 301 run(); 302 } 303 return 0; 304 } 305 ``` 306 307 ## [1801C - Music Festival](/contest/1801/problem/C "Codeforces Round 857 (Div. 1)") 308 309 Idea: [vaaven](/profile/vaaven "Master vaaven"), Preparation: [ViktorSM](/profile/ViktorSM "Expert ViktorSM") 310 311 **Solution** 312 313 Let's introduce the concept of a compressed album for an album, which is obtained from the original one by removing all elements except those that are the first maxima on their corresponding prefixes. 314 315 For example: 316 317 For the album $[\textbf{1}, \textbf{4}, 4, 3, \textbf{6}, 5, 6]$ the album will be compressed $[1, 4, 6]$. 318 319 Now we note that the solution of the original problem is reduced to solving the same problem, but on compressed albums. Indeed, the answer to them will not be different, because if some element increased the impression on ordinary albums, then it will increase if you compress albums and vice versa. Next, it will be assumed that all albums have been compressed beforehand. 320 321 Let's introduce $dp_c$ — the maximum impression that can be obtained if there were no albums such that they have elements larger than $c$. Then, $dp_c$ is equal to $dp_{c-1}$, or you can add another element or two if $c$ is the maximum element for some album. Then for all compressed albums, it can be recalculated through the value of $dp$ at the point before the first element of the album, or through $c - 1$. Thus, for recalculation, it is enough to know for each $c$ which albums ended in this index, as well as for each album its first element. Solution for $O(K)$ 322 323 Let's now solve the complete problem. For each value of $c$, let's remember the indexes of albums that contain an element equal to $c$. We go in order of increasing $c$, we maintain for each album the value of $dp_i$ — the maximum impression that can be obtained if there were no elements of large $c$ and Masha listened to the last $i$ album. Suppose for the next $c$ there is an album $i$, that there is a song with the coolness of $c$ in it. Then $dp_i$ should be taken as the maximum of $dp_i + 1$ and the values for all $dp_j + 1$, such that the maximum element in the $j$th album is less than the maximum element of $i$th, since she could listen to this track, either next in this album, or after listening to some other album completely. Note that you can store the value of $mx$ — maximum for all albums for which the maximum value in them is less than $c$ and recalculate it when moving to $c + 1$, storing those albums that have ended, then you will get a solution for $O(K + C)$. 324 325 **Code** 326 327 ``` 328 #include "bits/stdc++.h" 329 #include <algorithm> 330 #include <locale> 331 #include <random> 332 #include <unordered_map> 333 #include <vector> 334 335 using namespace std; 336 337 #define all(x) x.begin(), x.end() 338 #define rall(x) x.rbegin(), x.rend() 339 typedef long long ll; 340 typedef long double db; 341 typedef unsigned long long ull; 342 343 vector<int> shrink(vector<int> &a) { 344 vector<int> a1; 345 int n = a.size(); 346 int mx = 0; 347 for (int i = 0; i < n; ++i) { 348 if (a[i] > mx) { 349 a1.emplace_back(a[i]); 350 mx = a[i]; 351 } 352 } 353 return a1; 354 } 355 356 void solve() { 357 int n; 358 cin >> n; 359 vector<vector<int>> a(n); 360 int k; 361 for (int i = 0; i < n; ++i) { 362 int k; 363 cin >> k; 364 a[i].resize(k); 365 for (auto &j : a[i]) { 366 cin >> j; 367 } 368 } 369 vector<vector<int>> a1(n); 370 for (int i = 0; i < n; ++i) { 371 a1[i] = shrink(a[i]); 372 } 373 map<int, vector<int>> b; 374 for (int i = 0; i < n; ++i) { 375 for (auto &j : a1[i]) { 376 b[j].emplace_back(i); 377 } 378 } 379 vector<int> dp(n); 380 int closed = 0; 381 for (auto &it : b) { 382 int c = it.first; 383 int newclosed = 0; 384 for (auto &i : it.second) { 385 if (c == a1[i].back()) { 386 dp[i] = max(dp[i] + 1, closed + 1); 387 newclosed = max(newclosed, dp[i]); 388 continue; 389 } 390 if (c == a1[i].front()) { 391 dp[i] = closed + 1; 392 continue; 393 } 394 dp[i] = max(dp[i] + 1, closed + 1); 395 } 396 closed = max(closed, newclosed); 397 } 398 cout << *max_element(all(dp)); 399 } 400 401 signed main() { 402 int t = 0; 403 cin >> t; 404 while (t --> 0) { 405 solve(); 406 cout << '\n'; 407 } 408 return 0; 409 } 410 ``` 411 412 ## [1801D - The way home](/contest/1801/problem/D "Codeforces Round 857 (Div. 1)") 413 414 Idea: [Tikhon228](/profile/Tikhon228 "Master Tikhon228"), Preparation: [Ormlis](/profile/Ormlis "Legendary Grandmaster Ormlis") 415 416 **Solution** 417 418 Note that the show can be done "postponed". As soon as we don't have enough money to walk along the edge, we can do several shows in advance among the peaks that we have already passed, so as to earn the maximum amount of money. 419 420 For the general case, you can write $dp[v][best] = (\textit{min show}, \textit{max money})$, where $v$ is the number of the vertex where we are, and $best$ is the vertex with max. $w_i$, which we have already passed through. It can be shown that it is optimal to minimize the number of shows first, and then maximize the amount of money. This dynamics can be recalculated using Dijkstra's algorithm. Asymptotics of $O(mn\log n)$ 421 422 **Code** 423 424 ``` 425 #include "bits/stdc++.h" 426 427 #define rep(i, n) for (int i = 0; i < (n); ++i) 428 #define pb push_back 429 #define all(a) (a).begin(), (a).end() 430 #define ar array 431 #define vec vector 432 433 using namespace std; 434 435 using ll = long long; 436 using pi = pair<int, int>; 437 438 using vi = vector<int>; 439 using vpi = vector<pair<int, int>>; 440 441 const ll INF = 2e18; 442 const int maxN = 3e5 + 10; 443 444 struct PathParams { 445 ll num_show; 446 int money; 447 }; 448 449 bool operator==(const PathParams &a, const PathParams &b) { 450 return tie(a.num_show, a.money) == tie(b.num_show, b.money); 451 } 452 453 bool operator!=(const PathParams &a, const PathParams &b) { 454 return !(a == b); 455 } 456 457 struct State { 458 PathParams params; 459 int v; 460 int best; 461 }; 462 463 bool operator<(const PathParams &a, const PathParams &b) { 464 if (a.num_show != b.num_show) return a.num_show < b.num_show; 465 return a.money > b.money; 466 } 467 468 bool operator<(const State &a, const State &b) { 469 return tie(a.params, a.v, a.best) < tie(b.params, b.v, b.best); 470 } 471 472 bool operator>(const State &a, const State &b) { 473 return !(a < b); 474 } 475 476 void solve() { 477 int n, m, p, group; 478 cin >> n >> m >> p; 479 vector dp(n, vector<PathParams>(n, {INF, 0})); 480 vector<vpi> g(n); 481 vi w(n); 482 rep(i, n) cin >> w[i]; 483 rep(i, m) { 484 int a, b, s; 485 cin >> a >> b >> s; 486 a--; 487 b--; 488 g[a].emplace_back(b, s); 489 } 490 dp[0][0] = {0, p}; 491 priority_queue<State, vector<State>, greater<>> pq; 492 pq.push({.params = {.num_show=0, .money=p}, .v = 0, .best=0}); 493 while (!pq.empty()) { 494 auto current = pq.top(); 495 pq.pop(); 496 int v = current.v; 497 int best = current.best; 498 if (dp[v][best] != current.params) continue; 499 for (auto &[u, s]: g[v]) { 500 auto state2 = current; 501 PathParams &path = state2.params; 502 if (path.money < s) { 503 ll need = (s - path.money + w[best] - 1) / w[best]; 504 path.num_show += need; 505 path.money += need * w[best]; 506 assert(path.money < s + w[best]); 507 } 508 path.money -= s; 509 state2.v = u; 510 if (w[u] > w[state2.best]) state2.best = u; 511 if (path < dp[u][state2.best]) { 512 dp[u][state2.best] = path; 513 pq.push(state2); 514 } 515 } 516 } 517 ll ans = INF; 518 rep(i, n) { 519 ans = min(ans, dp[n - 1][i].num_show); 520 } 521 cout << (ans == INF ? -1 : ans) << '\n'; 522 } 523 524 signed main() { 525 int t = 1; 526 cin >> t; 527 rep(_, t) { 528 solve(); 529 } 530 return 0; 531 } 532 ``` 533 534 ## [1801E - Gasoline prices](/contest/1801/problem/E "Codeforces Round 857 (Div. 1)") 535 536 Idea and preparation: [Kirill22](/profile/Kirill22 "International Grandmaster Kirill22") 537 538 **Solution** 539 540 To begin with, let's understand what is required of us. A tree is given, in each vertex of which the price range for this vertex is recorded. A query is a pair of paths of equal length, the prices at the $i$-th vertices along these paths should be equal for all $i$. We need to find the number of ways to place prices at the vertices for each prefix of restrictions 541 542 Let's start with a slow solution of the problem. We will store the connectivity components (in each vertex prices should be equal). For each of them, we store an acceptable price range. The answer will be the product of the lengths of the ranges over all components. We will go along the paths and combine 2 vertices into one component using DSU. It is clear that to speed up this solution, it is necessary to search faster for the moments when two vertices are combined into one component. 543 544 First, let's analyze the long solution. Let's make a heavy-light decomposition, with which we will hash the paths in the tree, taking the root number of its components as a symbol for the vertex. Now, with the help of bin search, we will look for the first moment when the hashes on the path prefixes differ, that is, two vertices are combined into one component. With the help of transfusions, we will update the roots of their components for vertices and the tree of segments for hld. We will get $n$ unions, we will find each one for $O(log^2(n))$ using hld. There will also be $O(n\cdot log(n))$ updates in the segment tree due to overflows. For each request there will be $O(log^2(n))$ from hld. The final asymptotic $O((n+q)\cdot log^2(n))$ 545 546 Now let's give a beautiful solution to this problem. Let's start with bamboo. 547 548 Replace the equality of prices on a pair of paths with two pairs of paths with lengths equal to the maximum power of two, less than the length of the original path (as in sparse table). Now the path lengths of all constraints have become powers of two. We will iterate over the powers of two in descending order $2^k$, for each path of length $2^k$ we will get a vertex in the graph, we will also get a vertex for each such path in reverse order. Now the constraints define edges in such a graph. Let's spend them, select the spanning tree. For each edge from the backbone, we divide the constraints into 2 constraints with path lengths half as long and continue the process. On a layer with lengths 1, we will get the spanning tree we need, which will be responsible for the first moments when some pairs of vertices were combined into components. Note that no more than $2n$ edges will be added down from each layer, as well as no more than $2q$ edges from queries. That is, each layer will work for $O((n + q)\cdot\alpha(n))$, where $\alpha(n)$ is the average operating time in DSU, the inverse of the Ackerman function. We got the solution in $O((n + q) \cdot\alpha(n)\cdot log(n))$ 549 550 For a complete solution on the tree, first we divide a pair of paths into three pairs of corresponding vertical paths (take from the 4 end vertices of these paths the pair of vertices closest to the lca on its path, then we pair this path with a vertical path (part of another path), now we get one vertical path and an arbitrary path in the tree, let's split the second path by lca and the first by the corresponding lengths). Next, we will proceed similarly to bamboo, only the place of the vertex responsible for the segment, we will get the vertex responsible for the binary ascent in the tree to a height equal to the power of two. 551 552 **Code** 553 554 ``` 555 #include "bits/stdc++.h" 556 557 using namespace std; 558 559 const int mod = (int) 1e9 + 7; 560 561 int inv(int x) { 562 int res = 1, n = mod - 2; 563 while (n) { 564 if (n & 1) { 565 res = res * 1ll * x % mod; 566 } 567 x = x * 1ll * x % mod; 568 n /= 2; 569 } 570 return res; 571 } 572 573 const int N = (int) 2e5 + 22, K = 18; 574 vector<int> g[N]; 575 pair<int, int> a[N]; 576 int n, q, ans = 1; 577 int h[N], up[N][K], lg[N]; 578 vector<array<int, 3>> graph[K]; // lower vertex1, lower vertex2, time, vertex with direction 579 vector<array<int, 3>> gr[N]; 580 vector<array<int, 3>> edges; 581 582 struct dsu { 583 vector<int> p, sz; 584 585 void build(int n) { 586 p.resize(n); 587 sz.resize(n); 588 for (int i = 0; i < n; i++) { 589 p[i] = i; 590 sz[i] = 1; 591 } 592 } 593 594 int get(int v) { 595 return (v == p[v] ? v : p[v] = get(p[v])); 596 } 597 598 bool merge(int v, int u) { 599 v = get(v), u = get(u); 600 if (v != u) { 601 if (sz[v] > sz[u]) { 602 swap(v, u); 603 } 604 p[v] = u; 605 sz[u] += sz[v]; 606 return true; 607 } 608 return false; 609 } 610 } G, dsu[K]; 611 612 void dfs(int v, int pr, int d) { 613 h[v] = d; 614 up[v][0] = pr; 615 for (int j = 1; j < K; j++) { 616 up[v][j] = up[up[v][j - 1]][j - 1]; 617 } 618 for (auto u : g[v]) { 619 dfs(u, v, d + 1); 620 } 621 } 622 623 int la(int v, int x) { 624 for (int j = 0; j < K; j++) { 625 if (x >> j & 1) { 626 v = up[v][j]; 627 } 628 } 629 return v; 630 } 631 632 int lca(int v, int u) { 633 if (h[v] > h[u]) { 634 swap(v, u); 635 } 636 u = la(u, h[u] - h[v]); 637 if (v == u) { 638 return v; 639 } 640 for (int j = K - 1; j >= 0; j--) { 641 if (up[v][j] != up[u][j]) { 642 v = up[v][j], u = up[u][j]; 643 } 644 } 645 return up[v][0]; 646 } 647 648 int id(int v) { 649 return (v > 0 ? v : -v + n); 650 } 651 652 int sgn(int v) { 653 return (v > 0 ? 1 : -1); 654 } 655 656 void add_edge(int j, int v, int u, int t) { 657 if (dsu[j].merge(id(v), id(u))) { 658 if (j > 0) { 659 if (sgn(v) == sgn(u)) { 660 add_edge(j - 1, v, u, t); 661 add_edge(j - 1, sgn(v) * up[abs(v)][j - 1], sgn(u) * up[abs(u)][j - 1], t); 662 } else { 663 if (sgn(v) == -1) { 664 swap(v, u); 665 } 666 add_edge(j - 1, v, sgn(u) * up[abs(u)][j - 1], t); 667 add_edge(j - 1, sgn(v) * up[abs(v)][j - 1], u, t); 668 } 669 } else { 670 edges.push_back({abs(v), abs(u), t}); 671 } 672 } 673 } 674 675 void add(int v, int u, int x, int y, int t, int type1, int type2) { 676 if (h[v] < h[u]) { 677 swap(v, u); 678 } 679 if (h[x] < h[y]) { 680 swap(x, y); 681 } 682 assert(h[v] - h[u] == h[x] - h[y]); 683 int g = lg[h[v] - h[u]]; 684 if (type1 == type2) { 685 add_edge(g, type1 * v, type2 * x, t); 686 add_edge(g, type1 * la(v, h[v] - h[u] - (1 << g) + 1), type2 * la(x, h[x] - h[y] - (1 << g) + 1), t); 687 } else { 688 add_edge(g, type1 * v, type2 * la(x, h[x] - h[y] - (1 << g) + 1), t); 689 add_edge(g, type1 * la(v, h[v] - h[u] - (1 << g) + 1), type2 * x, t); 690 } 691 } 692 693 void merge(int v, int u) { 694 v = G.get(v), u = G.get(u); 695 if (v != u) { 696 G.merge(v, u); 697 if (G.sz[v] > G.sz[u]) { 698 swap(v, u); 699 } 700 if (a[v].first <= a[v].second) { 701 ans = ans * 1ll * inv(a[v].second - a[v].first + 1) % mod; 702 } 703 if (a[u].first <= a[u].second) { 704 ans = ans * 1ll * inv(a[u].second - a[u].first + 1) % mod; 705 } 706 a[u].first = max(a[u].first, a[v].first); 707 a[u].second = min(a[u].second, a[v].second); 708 if (a[u].first > a[u].second) { 709 ans = 0; 710 } else { 711 ans = ans * 1ll * (a[u].second - a[u].first + 1) % mod; 712 } 713 } 714 } 715 716 int main() { 717 ios_base::sync_with_stdio(0); 718 cin.tie(0); 719 cout.tie(0); 720 for (int j = 2; j < N; j++) { 721 lg[j] = lg[j / 2] + 1; 722 } 723 cin >> n; 724 for (int i = 2; i <= n; i++) { 725 int v; 726 cin >> v; 727 g[v].push_back(i); 728 } 729 for (int i = 1; i <= n; i++) { 730 cin >> a[i].first >> a[i].second; 731 ans = ans * 1ll * (a[i].second - a[i].first + 1) % mod; 732 } 733 dfs(1, 1, 0); 734 cin >> q; 735 for (int j = 0; j < K; j++) { 736 dsu[j].build(2 * n + 1); 737 } 738 for (int i = 0; i < q; i++) { 739 int v, u, x, y; 740 cin >> v >> u >> x >> y; 741 int w = lca(v, u); 742 int z = lca(x, y); 743 if (h[v] - h[w] > h[x] - h[z]) { 744 swap(v, x); 745 swap(u, y); 746 swap(w, z); 747 } 748 if (v != w) { 749 int d = h[v] - h[w]; 750 int v2 = la(v, d - 1); 751 int x2 = la(x, d - 1); 752 add(v, v2, x, x2, i, 1, 1); 753 v = up[v2][0]; 754 x = up[x2][0]; 755 } 756 if (x != z) { 757 int d = h[x] - h[z]; 758 int v2 = la(u, (h[u] - h[v]) - d); 759 int x2 = la(x, d - 1); 760 add(v, up[v2][0], x, x2, i, -1, 1); 761 v = v2; 762 x = up[x2][0]; 763 } 764 add(v, u, x, y, i, (h[v] > h[u] ? 1 : -1), (h[x] > h[y] ? 1 : -1)); 765 } 766 G.build(n + 1); 767 int j = 0; 768 for (int i = 0; i < q; i++) { 769 while (j < (int) edges.size() && edges[j][2] == i) { 770 merge(edges[j][0], edges[j][1]); 771 j++; 772 } 773 cout << ans << '\n'; 774 } 775 } 776 ``` 777 778 ## [1801F - Another n-dimensional chocolate bar](/contest/1801/problem/F "Codeforces Round 857 (Div. 1)") 779 780 Idea and preparation: [Tikhon228](/profile/Tikhon228 "Master Tikhon228") 781 782 **Solution** 783 784 For $A$ we denote the maximum value of $a_i$ 785 786 To begin with, let's solve the problem for $O(n\cdot k\cdot f(k, A))$ using dynamic programming. 787 788 Let's put $dp[i][j]$— the maximum possible volume of the smallest piece, if by the first $i$ measurements we divided the chocolate into $j$ parts. If we have divided into more than $k$ parts, we will also put the result in $dp[i][k]$. In terms of calculation, we need to decide how many hours to divide the chocolate bar along the next dimension. Let's look at several ways to do this. 789 790 * It is possible for $O(k)$ to sort out the state to which we are moving, and from this calculate how many parts you need to divide the chocolate bar along the next dimension. — We get $O(n\cdot k^2)$ 791 * It is possible for $O(A)$ to sort out how many parts we divide the chocolate bar along the next dimension. 792 * Being in the state of $dp[i][j]$, you can iterate over $b_i$ — into how many parts to divide the chocolate until $j\cdot b_i\le k$. It can be shown that such a solution will work for $O(n\cdot k\cdot\ln{k})$ 793 794 The key idea 795 796 * suppose we need to divide a chocolate bar into $10$ parts, and along the first measurements we have already divided it into $5$ parts, or $6$ parts, or $7, 8$ or $9$ parts. All these states are not distinguishable for us, because in all these cases we need to divide the chocolate bar into at least $2$ parts. It remains to understand how many such <> states there are and learn how to store them. There are several approaches for this, let's analyze one of them: 797 * we are interested in all the values of $\lceil\frac{k}{i}\rceil$ for $i = 1, 2, \ldots k$— this is how many parts the chocolate bar may still need to be divided into. Among them, only $O(\sqrt{k})$different, since either $i\le\sqrt{k}$, or the value of $\lceil\frac{k}{i}\rceil\le\sqrt{k}$ itself. If we make all these numbers states, and recalculate, iterating over the state to which to go, we get $O(n\cdot\sqrt{k} \cdot\sqrt{k}) = O(n\cdot k)$— this is still not enough to solve the hollow problem. 798 799 Last observation 800 801 If we are in the state of $dp[i][remain]$ where $remain = \lceil\frac{k}{i}\rceil$ for some $i$, we will apply the same idea to it. From it, we are interested in transitions to the states $\lceil \frac{remain}{j} \rceil$ for $j = 1, 2, \ldots remain$. What kind of asymptotics will be obtained if we iterate over only interesting transitions? 802 803 $n \cdot (\sum\limits_{r=1}^{\sqrt{k}}{ 2 \cdot \sqrt{r} + 2 \cdot \sqrt{\lceil \frac{k}{r} \rceil}})$ 804 805 * it can be shown that this is $O(n\cdot k^{3/4})$— which solves the problem 806 807 **Code** 808 809 ``` 810 #include <bits/stdc++.h> 811 using namespace std; 812 813 const int MAXN = 200; 814 int a[MAXN]; 815 816 const int MAXK = 1e7 + 100, MAXH = 1e4; 817 int hsh[MAXK]; 818 int rev[MAXH]; 819 820 double dp[MAXN][MAXH]; 821 822 vector<array<int, 2>> go[MAXH]; 823 824 main() { 825 ios_base::sync_with_stdio(false); 826 cin.tie(0); cout.tie(0); 827 int n, k; 828 cin >> n >> k; 829 for (int i = 0; i < n; ++i) { 830 cin >> a[i]; 831 } 832 int id = 0; 833 for (int c = 1;; ++id) { 834 rev[id] = (k + c - 1) / c; 835 hsh[(k + c - 1) / c] = id; 836 int t = (k + c - 1) / c - 1; 837 if (t == 0) break; 838 c = (k + t - 1) / t; 839 } 840 ++id; 841 dp[0][hsh[k]] = k; 842 843 for (int i = 0; i < id; ++i) { 844 int k = rev[i]; 845 for (int c = 1;;) { 846 go[i].push_back({c, hsh[(k + c - 1) / c]}); 847 int t = (k + c - 1) / c - 1; 848 if (t == 0) break; 849 c = (k + t - 1) / t; 850 } 851 } 852 853 for (int i = 0; i < n; ++i) { 854 for (int j = 0; j < id; ++j) { 855 double val = dp[i][j]; 856 if (val == 0) continue; 857 for (auto elem : go[j]) { 858 int c = elem[0], k1 = elem[1]; 859 if (c > a[i]) break; 860 int cur = a[i] / c; 861 dp[i + 1][k1] = max(dp[i + 1][k1], val * cur / a[i]); 862 } 863 } 864 } 865 cout << fixed << setprecision(20); 866 cout << dp[n][hsh[1]] << '\n'; 867 return 0; 868 } 869 ``` 870 871 ## [1801G - A task for substrings](/contest/1801/problem/G "Codeforces Round 857 (Div. 1)") 872 873 Idea and preparation: [grphil](/profile/grphil "Master grphil") 874 875 **Solution** 876 877 Let's use the Aho-Korasik structure to store strings from $S$. Let's build compressed suffix links on it. This way it is a little more optimal to find all the lines from $S$ ending in this position $t$. 878 879 Denote by $pref[i]$ the number of substrings of $S$ in the prefix $t$ of length $i$. 880 881 Denote by $suf[i]$ the number of substrings of $S$ in the suffix $t$ starting from the position $i$. 882 883 Note that $pref[r] + suf[l] - priv[|T|]$ is equal to the number of substrings of the string for $t$ from $S$ on the segment $[l, p]$ minus the number of substrings of $t$ from $S$ that begin before $l$ and end later than $r$. 884 885 For each query, we will find a substring $t$ that matches $s_i$, which covers the string $t[l, r]$ and ends as close as possible to $r$. If there is no such thing, then the answer can be calculated using the previous formula. Otherwise, $t[l, r]$ is invested in $s_i[l', r']$. At the same time, there are no substrings of $S$ in the string $s_i$ that begin before $l'$ and end later than $r'$. To get the answer, we apply the previous formula with the string $s_i$ and the sub-section $[l', r']$. 886 887 Asymptotics: $O(S+ t +m \log m)$ 888 889 **Code** 890 891 ``` 892 #include <bits/stdc++.h> 893 894 #define x first 895 #define y second 896 897 using namespace std; 898 899 struct node { 900 int nx[26]; 901 int p; 902 int pp; 903 int len; 904 int id; 905 int cnt; 906 bool term; 907 908 node() : p(-1), pp(-1), len(0), id(-1), term(false), cnt(0) { 909 for (int i = 0; i < 26; i++) { 910 nx[i] = -1; 911 } 912 } 913 }; 914 915 vector<node> g; 916 917 vector<string> s[2]; 918 919 string t[2]; 920 921 vector<vector<long long>> c[2], pid[2]; 922 923 vector<long long> tc[2]; 924 925 int add(int a, char c) { 926 c -= 'a'; 927 if (g[a].nx[c] == -1) { 928 g[a].nx[c] = g.size(); 929 g.emplace_back(); 930 g.back().len = g[a].len + 1; 931 } 932 return g[a].nx[c]; 933 } 934 935 void build_aho(int a) { 936 vector<pair<int, int>> q; 937 for (int i = 0; i < 26; i++) { 938 if (g[a].nx[i] == -1) { 939 g[a].nx[i] = a; 940 } else { 941 q.emplace_back(a, i); 942 } 943 } 944 945 int qb = 0; 946 while (qb < q.size()) { 947 int b = q[qb].x; 948 int i = q[qb].y; 949 qb++; 950 int v = g[b].nx[i]; 951 int c = g[b].p; 952 953 if (g[v].term) { // bug in c != -1 954 g[v].cnt = 1; 955 } 956 957 if (c == -1) { 958 g[v].p = a; 959 g[b].pp = -1; 960 } else { 961 g[v].p = g[c].nx[i]; 962 if (g[v].term) { 963 g[v].pp = v; 964 } else { 965 g[v].pp = g[g[v].p].pp; 966 } 967 g[v].cnt += g[g[v].p].cnt; 968 } 969 970 for (int i = 0; i < 26; i++) { 971 if (g[v].nx[i] == -1) { 972 g[v].nx[i] = g[g[v].p].nx[i]; 973 } else { 974 q.emplace_back(v, i); 975 } 976 } 977 } 978 } 979 980 vector<vector<pair<int, int>>> ts; 981 vector<int> qlen; 982 priority_queue<pair<int, int>> h; 983 vector<long long> ans; 984 985 long long get_ans(int rdst, int len, vector<long long>& a, vector<long long>& b, bool substr) { 986 int l = a.size() - 1 - rdst; 987 int r = l + len; 988 long long cnt = a[r] + b[a.size() - 1 - l] - a.back(); 989 if (substr && l == 0 && r == a.size() - 1) { 990 cnt++; 991 } 992 993 return cnt; 994 } 995 996 int main() { 997 ios_base::sync_with_stdio(0); 998 cin.tie(0); 999 cout.tie(0); 1000 1001 int n, m; 1002 cin >> n >> m; 1003 g.emplace_back(); g.emplace_back(); 1004 s[0].resize(n); s[1].resize(n); 1005 c[0].resize(n); c[1].resize(n); 1006 pid[0].resize(n); pid[1].resize(n); 1007 ans.resize(m); 1008 1009 cin >> t[0]; 1010 t[1] = t[0]; 1011 reverse(t[1].begin(), t[1].end()); 1012 ts.resize(t[0].size()); 1013 1014 for (int i = 0; i < n; i++) { 1015 cin >> s[0][i]; 1016 } 1017 sort(s[0].begin(), s[0].end(), \ 1018 [](const string& a, const string& b) { return a.size() < b.size(); }); 1019 1020 for (int i = 0; i < n; i++) { 1021 s[1][i] = s[0][i]; 1022 reverse(s[1][i].begin(), s[1][i].end()); 1023 1024 for (int e = 0; e < 2; e++) { 1025 int a = e; 1026 for (auto j : s[e][i]) { 1027 a = add(a, j); 1028 } 1029 g[a].term = true; 1030 g[a].id = i; 1031 } 1032 } 1033 1034 build_aho(0); build_aho(1); 1035 1036 for (int e = 0; e < 2; e++) { 1037 tc[e].resize(t[0].size() + 1); 1038 1039 int a = e; 1040 for (int i = 0; i < t[0].size(); i++) { 1041 a = g[a].nx[t[e][i] - 'a']; 1042 tc[e][i + 1] = tc[e][i] + g[a].cnt; 1043 } 1044 for (int i = 0; i < n; i++) {; 1045 c[e][i].resize(s[0][i].size() + 1); 1046 pid[e][i].resize(s[0][i].size() + 1, -1); 1047 1048 int a = e; 1049 for (int j = 0; j < s[e][i].size(); j++) { 1050 a = g[a].nx[s[e][i][j] - 'a']; 1051 c[e][i][j + 1] = c[e][i][j] + g[a].cnt; 1052 1053 if (g[a].term) { // bug always 1054 pid[e][i][j + 1] = g[a].id; 1055 } 1056 } 1057 1058 for (int j = (int)s[e][i].size() - 1; j >= 0; j--) { // bug forget 1059 if (pid[e][i][j] == -1) { 1060 pid[e][i][j] = pid[e][i][j + 1]; 1061 } 1062 } 1063 c[e][i].back()--; // bug forget string itself 1064 1065 } 1066 } 1067 1068 for (int i = 0; i < m; i++) { 1069 int a, b; 1070 cin >> a >> b; 1071 a--; 1072 ts[b - 1].emplace_back(a, i); 1073 qlen.emplace_back(b - a); 1074 } 1075 1076 int a = 0; 1077 for (int i = 0; i < t[0].size(); i++) { 1078 // cout << i << ' ' << t[0][i] << '\n'; 1079 for (auto j : ts[i]) { 1080 h.emplace(j); 1081 } 1082 1083 a = g[a].nx[t[0][i] - 'a']; 1084 1085 if (g[a].pp != -1) { // bug ignore 1086 int id = g[g[a].pp].id; 1087 int bg = i + 1 - (int)s[0][id].size(); 1088 while (h.size() > 0 && h.top().x >= bg) { 1089 int rdst = i - h.top().x + 1; 1090 int nid = pid[1][id][rdst]; // bug forget 1091 1092 // cout << h.top().x << ' ' << h.top().y << ' ' << rdst << ' ' << nid << '\n'; 1093 1094 ans[h.top().y] = get_ans(rdst, qlen[h.top().y], 1095 c[0][nid], c[1][nid], true); 1096 h.pop(); 1097 } 1098 } 1099 } 1100 1101 while (h.size() > 0) { 1102 // cout << h.top().x << ' ' << h.top().y << '\n'; 1103 ans[h.top().y] = get_ans(t[0].size() - h.top().x, qlen[h.top().y], tc[0], tc[1], false); 1104 h.pop(); 1105 } 1106 1107 for (auto i : ans) { 1108 cout << i << ' '; 1109 } 1110 cout << '\n'; 1111 } 1112 ```