codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```