codeforces-scrape

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

1853.md (43863B)


      1 Source: https://codeforces.com/blog/entry/116940
      2 
      3 We hope you enjoyed these problems :) This contest has been in the works for almost a year.
      4 
      5 **About the Authors**
      6 
      7 This round was mostly made possible by problemsetters from the [CerealCodes](https://www.cerealcodes.org/) initiative!
      8 
      9 CerealCodes is an organization based in the United States dedicated to running high quality competitive programming contests. You can check out our previous contest [here](https://codeforces.com/gym/103886).
     10 
     11 **UPD: D1D Editorial have been updated**
     12 
     13 **UPD 2: D1D Editorial now has images by [EmeraldBlock](/profile/EmeraldBlock "Master EmeraldBlock"). As an apology gift for being so slow, the image generator is programmatic and available [here](https://artofproblemsolving.com/texer/codeforces).**
     14 
     15 #### [1853A - Desorting](/contest/1853/problem/A "Codeforces Round 887 (Div. 2)")
     16 
     17 Problem Credits: [buffering](/profile/buffering "Expert buffering")
     18 
     19 Analysis: [buffering](/profile/buffering "Expert buffering")
     20 
     21 **Hint 1**
     22 
     23 To make $a$ not sorted, we just need to pick one index $i$ so $a_i \gt a_{i + 1}$. How do we do this?
     24 
     25 **Solution**
     26 
     27 To make $a$ not sorted, we just have to make $a_i \gt a_{i + 1}$ for one $i$.
     28 
     29 In one operation, we can reduce the gap between two adjacent elements $i, i + 1$ by $2$ by adding $1$ to $1 \dots i$ and subtracting $1$ from ${i + 1} \dots n$.
     30 
     31 It is clearly optimal to pick the smallest gap between a pair of adjacent elements to minimize the number of operations we have to do. If we have $a_i = x, a_{i + 1} = y$, we can make $x \gt y$ within $\lfloor \frac{(y - x)}{2} \rfloor + 1$ operations.
     32 
     33 Thus, we can just go through $a$, find the minimum difference gap, and calculate the minimum operations using the above formula. Note that if $a$ is not sorted, we can just output $0$.
     34 
     35 The time complexity is $O(n)$.
     36 
     37 **Code (C++)**
     38 
     39 ```
     40 #include <bits/stdc++.h>
     41 #include <numeric>
     42 using namespace std;
     43  
     44 int main(){
     45  
     46     ios::sync_with_stdio(false);
     47     cin.tie(0);
     48  
     49     int T; cin >> T;
     50  
     51     while (T--) {
     52  
     53         int n; cin >> n;
     54         vector<int> nums(n);
     55         int diff = 1e9;
     56         bool sorted = true;
     57         for (int i = 0; i < n; i++) {
     58             cin >> nums[i];
     59             if (i > 0) {
     60                 diff = min(nums[i] - nums[i - 1], diff);
     61                 sorted &= nums[i] >= nums[i - 1];
     62             }
     63         }
     64         
     65         if (!sorted) {
     66             cout << 0 << endl;
     67             continue;
     68         }
     69     
     70         cout << diff/2 + 1 << endl;
     71     }
     72 }
     73 ```
     74 
     75 #### [1853B - Fibonaccharsis](/contest/1853/problem/B "Codeforces Round 887 (Div. 2)")
     76 
     77 Problem Credits: [ntarsis30](/profile/ntarsis30 "Specialist ntarsis30"), [cry](/profile/cry "Candidate Master cry")
     78 
     79 Analysis: [cry](/profile/cry "Candidate Master cry")
     80 
     81 **Hint 1**
     82 
     83 Can a sequence involving $n$, which is up to $10^5$, really have up to $10^9$ terms?
     84 
     85 **Solution**
     86 
     87 The terms of the fibonacci sequence will increase exponentially. This is quite intuitive, but mathematically, fibonnaci-like sequences will increase at a rate of phi to the power of $n$, where phi (the golden ratio) is about $1.618$. Thus, the maximum number of terms a sequence can have before it reaches $10^9$, or the maximum value of $n$, is pretty small (around $\log n$).
     88 
     89 Instead of trying to fix the first two elements of the sequence and counting how many sequences $s$ will have $s_k = n$, note that we already have $n$ fixed. If we loop over the $k-1$th element of the sequence, the sequence is still fixed. If we know the $x$th element and $x-1$th element of $s$, we can find that $s_{x - 2} = s_{x} - s_{x - 1}$.
     90 
     91 Thus, we can just go backwards and simulate for $k$ iterations in $O(\log n)$ since $k$ is small, breaking at any point if the current sequence is not fibonnaci-like (there are negative elements or it is not strictly increasing). Otherwise, we add $1$ to our answer.
     92 
     93 The time complexity is $O(n \cdot \log n)$.
     94 
     95 **Code (C++)**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99 using namespace std;
    100  
    101 int main()
    102 {
    103     ios::sync_with_stdio(false);
    104     cin.tie(0);
    105     
    106     int T; cin >> T;
    107     
    108     while (T--) {
    109  
    110         int n; int k;
    111         cin >> n >> k;
    112      
    113         int ans = 0;
    114      
    115         for (int i = 1; i <= n; i++) {
    116             int second = n; //xth element where x is k
    117             int first = i; //fixing x-1th element where x is k-1
    118             bool valid_seq = true;
    119             for (int j = 0; j < k - 2; j++) {
    120                 //for s_x and s_x-1, s_x-2 = s_x - s_x-1
    121                 int fx = first;
    122                 first = second - fx;
    123                 second = fx;
    124                 valid_seq &= first <= second;
    125                 valid_seq &= min(first, second) >= 0;
    126                 if (!valid_seq) break; //break if the sequence is not fibonacci-like
    127             }
    128             if (valid_seq) ans++;
    129         }
    130  
    131         cout << ans << endl;
    132     }
    133  
    134 }
    135 ```
    136 
    137 Bonus: Solve for $n, k \leq 10^9$
    138 
    139 **Bonus Solution**
    140 
    141 Analysis by [awesomeguy856](/profile/awesomeguy856 "Candidate Master awesomeguy856")
    142 
    143 $f[k] = F_{k-2}f[0]+F_{k-1}f[1]$
    144 
    145 By the Extended Euclidean Algorithm, we can find one integral solution for this equation, since $\gcd (F_{k-2}, F_{k-1}) = 1 | f[k].$ Let this solution be $(f[0], f[1]) = (x, y).$ Then all other integral solutions are in the form $(x+cF_{k-1}, y-cF_{k-2}),$ for $c \in Z$ so we can find all valid solutions by binary search on $f[1],f[0] \geq 0$ and $f[1] \gt f[0]$, or just by some calculations.
    146 
    147 #### [1852A - Ntarsis' Set](/contest/1852/problem/A "Codeforces Round 887 (Div. 1)")
    148 
    149 Problem Credits: [nsqrtlog](/profile/nsqrtlog "Expert nsqrtlog")
    150 
    151 Analysis: [nsqrtlog](/profile/nsqrtlog "Expert nsqrtlog"), [buffering](/profile/buffering "Expert buffering")
    152 
    153 **Hint 1**
    154 
    155 Suppose that the numbers are arranged in a line in increasing order. Take a look at each number $x$ before some day. If it isn't deleted on that day, what new position does it occupy, and how is that impacted by its previous position?
    156 
    157 **Answer**
    158 
    159 If $x$ is between $a_i$ and $a_{i+1}$, it will move to a new position of $x-i$, since $i$ positions before it are deleted.
    160 
    161 **Hint 2**
    162 
    163 Take this observation, and apply it to simulate the process backwards.
    164 
    165 **Solution**
    166 
    167 Suppose the numbers are arranged in a line in increasing order. Consider simulating backwards; instead of deleting the numbers at positions $a_1,a_2,\ldots,a_n$ in each operation, then checking the first number after $k$ operations, we start with the number $1$ at the front, try to insert zeroes right after positions $a_1-1, a_2-2, \ldots, a_{n}-n$ in each operation so that the zeroes will occupy positions $a_1, a_2, \ldots, a_n$ after the insertion, and after $k$ insertions, we will check the position that $1$ will end up at.
    168 
    169 If $a_1$ is not equal to $1$, the answer is $1$. Otherwise, each insertion can be processed in $O(1)$ if we keep track of how many of $a_1-1, a_{2}-2,\ldots,a_{n}-n$ are before the current position $x$ of $1$; if $a_1-1$ through $a_i-i$ are before $x$, then we will insert $i$ zeroes before $x$.
    170 
    171 The time complexity is $O(n+k)$ per test case. The editorial code additionally processes every insertion with the same $i$ value in $O(1)$, for $O(n)$ overall complexity.
    172 
    173 There are alternative solutions using binary search with complexity $O(k\log nk)$ or $O(k\log n\log nk)$, and we allowed them to pass. In fact, this problem was originally proposed with $k \leq 10^9$ but we lowered the constraints.
    174 
    175 **Code (C++) -- Model Solution**
    176 
    177 ```
    178 #include <bits/stdc++.h>
    179 using namespace std;
    180 
    181 int n, k, a[200010];
    182 
    183 void solve() {
    184     cin >> n >> k;
    185     for (int i = 0; i < n; i++) {
    186         cin >> a[i];
    187         a[i] -= i;
    188     }
    189     if (a[0] != 1) {
    190         cout << 1 << "\n";
    191         return;
    192     }
    193     a[n] = 2e9;
    194     //start at position 1, and find what number moves to its position
    195     long long ans = 1;
    196     int inc = 1; //how many zeroes to insert
    197     while (inc < n) {
    198         int days = (a[inc] - ans + inc - 1) / inc;
    199         if (days >= k){
    200             ans += k * inc;
    201             k = 0;
    202             break;
    203         }
    204         ans += days * inc;
    205         k -= days;
    206         while (a[inc] <= ans) inc++;
    207     }
    208     ans += 1ll * k * n;
    209     cout << ans << "\n";
    210 }
    211 
    212 int main() {
    213     ios::sync_with_stdio(0);
    214     cin.tie(nullptr);
    215     
    216     int t; cin >> t;
    217     while (t--) solve();
    218 }
    219 ```
    220 
    221 **Code (C++) -- Simulation (more readable)**
    222 
    223 ```
    224 #include <bits/stdc++.h>
    225 using namespace std;
    226 
    227 using ll = long long;
    228 const int inf = 1e9+10;
    229 const ll inf_ll = 1e18+10;
    230 #define all(x) (x).begin(), (x).end()
    231 #define pb push_back
    232 #define cmax(x, y) (x = max(x, y))
    233 #define cmin(x, y) (x = min(x, y))
    234 
    235 #ifndef LOCAL
    236 #define debug(...) 0
    237 #else
    238 #include "../../debug.cpp"
    239 #endif
    240 
    241 int main() {
    242     ios_base::sync_with_stdio(0); cin.tie(0);
    243     int t; cin >> t;
    244     while (t--) {
    245         ll n, k; cin >> n >> k;
    246         vector<ll> a(n);
    247         for (int i = 0; i < n; i++)
    248             cin >> a[i];
    249 
    250         ll j = 0, x = 1;
    251         while (k--) {
    252             while (j < n && a[j] <= x+j)
    253                 j++;
    254             x += j;
    255         }
    256 
    257         cout << x << "\n";
    258     }
    259 }
    260 ```
    261 
    262 #### [1852B - Imbalanced Arrays](/contest/1852/problem/B "Codeforces Round 887 (Div. 1)")
    263 
    264 Problem Credits: [nsqrtlog](/profile/nsqrtlog "Expert nsqrtlog")
    265 
    266 Analysis: [buffering](/profile/buffering "Expert buffering"), [nsqrtlog](/profile/nsqrtlog "Expert nsqrtlog")
    267 
    268 **Hint 1**
    269 
    270 You can solve the problem by picking one number from each pair $(n, -n)$, $(n - 1, -n + 1) \dots$, $(1, -1)$.
    271 
    272 **Hint 2**
    273 
    274 $b_i \gt b_j$ implies $a_i \gt a_j$.
    275 
    276 **Hint 3**
    277 
    278 First, try to determine **one** index in $O(n)$, or determine if that's impossible.
    279 
    280 **Hint 4**
    281 
    282 Sort the array $a$ to optimize the $O(n^2)$ solution.
    283 
    284 **Solution**
    285 
    286 At the start, let $x$ be an index such that $b_x$ has the greatest absolute value. If $b_x$ is negative, we have $a_x=0$, and else $a_x=n$. Moreover, we can't have $a_y=0,a_z=n$ for any indices $y$ and $z$, because that implies $b_y+b_z$ is both positive and negative, contradiction. Hence, the necessary and sufficient condition to check if we can determine an element in array $b$ with maximum absolute value is (there exists an element of array $a$ equal to $0$) xor (there exists an element of array $a$ equal to $n$). Then, we can remove that element and re-calculate the $a$ array, leading to an $O(n^2)$ solution. If the check fails at any moment, there is no valid solution.
    287 
    288 To optimize it further, note that we can sort array $a$ at the start and keep track of them in a deque-like structure. We only need to check the front and end of the deque to see if our key condition holds. Finally, we can use a variable to record the number of positive elements deleted so far and subtract it from the front and end of the deque when checking our condition, so that each check is $O(1)$. The overall complexity becomes $O(n\log n)$ due to sorting.
    289 
    290 **Code (C++)**
    291 
    292 ```
    293 #include <bits/stdc++.h>
    294 using namespace std;
    295 
    296 int n, ans[100010];
    297 vector<pair<int,int>> arr;
    298 
    299 void solve() {
    300     cin >> n;
    301     arr.resize(n);
    302     for (int i = 0; i < n; i++) {
    303         cin >> arr[i].first;
    304         arr[i].second = i;
    305     }
    306     sort(arr.begin(), arr.end());
    307     int l = 0, r = n - 1, sz = n;
    308     while (l <= r) {
    309         if ((arr[r].first == n - l) ^ (arr[l].first == n - 1 - r)) {
    310             if (arr[r].first == n - l) {
    311                 ans[arr[r--].second] = sz--;
    312             }
    313             else {
    314                 ans[arr[l++].second] = -(sz--);
    315             }
    316         }
    317         else {
    318             cout << "NO" << "\n";
    319             return;
    320         }
    321     }
    322     cout << "YES" << "\n";
    323     for (int i = 0; i < n; i++) cout << ans[i] << " ";
    324     cout << "\n";
    325 }
    326 
    327 int main() {
    328     ios::sync_with_stdio(0);
    329     cin.tie(nullptr);
    330 
    331     int t; cin >> t;
    332     while(t--) solve();
    333 }
    334 ```
    335 
    336 #### [1852C - Ina of the Mountain](/contest/1852/problem/C "Codeforces Round 887 (Div. 1)")
    337 
    338 Problem Credits: [fast-fourier-transfem](/profile/fast-fourier-transfem "Candidate Master fast-fourier-transfem")
    339 
    340 Analysis: [fast-fourier-transfem](/profile/fast-fourier-transfem "Candidate Master fast-fourier-transfem"), [EmeraldBlock](/profile/EmeraldBlock "International Master EmeraldBlock"), [GusterGoose27](/profile/GusterGoose27 "Master GusterGoose27")
    341 
    342 **Hint One**
    343 
    344 Suppose you knew in advance how many times each octopus will regenerate. Could you solve the problem then?
    345 
    346 **Solution**
    347 
    348 To make things easier, replace health values of $k$ with health values of $0$, so the goal is to reach $0$ health. Regeneration is now from $0$, which was formerly $k$, to $k-1$, instead of $1$ to $k$, which is now $1$ to $0$. For clarity, create a new array $b$ such that $b[i] = a[i] \% k$.
    349 
    350 Now, instead of letting health values wrap around, we can just initially give each octopus a multiple of $k$ more health. For example, if $k=3$ and an octopus with initially $2$ health regenerates twice, we can pretend it initially had $2 + 2 \cdot 3 = 8$ health.
    351 
    352 Create a new array $c$ storing these new healths. Since all healths will reach $0$, it also represents the number of boulders that will hit each octopus.
    353 
    354 To find the minimum number of boulder throws, represent the health values with a histogram, where the heights of blocks are equal to the values of $c$:
    355 
    356 ![ ](/predownloaded/e2/45/e2456fbec8ef27ad4ee24bcbc828879df2763d61.png)
    357 
    358 Then, erase all vertical borders between blocks. The resulting segments each represent a boulder throw:
    359 
    360 ![ ](/predownloaded/61/dd/61dd5605b382111e386f0ce71603ff13c33e99e6.png)
    361 
    362 Intuitively, this should minimize the number of boulders, since any sequence of boulder throws should be rearrangeable into horizontal segments covering this histogram.
    363 
    364 We can easily calculate the number of boulders as the sum of all **positive** adjacent differences, treating the far left and far right as having health $0$.
    365 
    366 ![ ](/predownloaded/84/07/8407a1f41639d504210e6e10a9e6587c70d151ca.png)
    367 
    368 Formally, pad $c$ with an extra $0$ to the left and right (i.e. $c[0] = c[n+1] = 0$) and let the adjacent differences be $d[i] = c[i+1]-c[i]$. We claim the minimum number of boulder throws is $\mathrm{throws} = \sum_{i=0}^n{\max\{d[i],0\}}$.
    369 
    370 * This many is necessary, since if $d[i]$ is positive, octopus $i+1$ gets crushed $d[i]$ more times than octopus $i$, so at least $d[i]$ boulders' ranges have left endpoint $l = i+1$.
    371 * This many is achievable, as depicted above. Crush all octopuses with the highest health exactly once (crushing consecutive octopuses with the same boulder), then all octopuses with the new highest health, and so on. Each boulder's range's left endpoint corresponds with part of a positive adjacent difference.
    372 
    373 **Hint 2**
    374 
    375 Can you figure out an $O(n^2)$ solution? And can you improve on it?
    376 
    377 **Hint 3**
    378 
    379 Suppose you already had the optimal solution for the subarray $a[1 \ldots i]$. How could you extend it to $a[1 \ldots i+1]$?
    380 
    381 **Tutorial**
    382 
    383 Read the solution in Hint One before continuing with this tutorial; it provides important definitions.
    384 
    385 To reduce the number of possibilities for each $c[i]$, we prove the following lemma: There exists an optimal choice of $c$ (minimizing $\mathrm{throws}$) where all differences between adjacent $c[i]$ have absolute value less than $k$.
    386 
    387 Intuitively, this is because we can decrease a $c[i]$ by $k$. Formally:
    388 
    389 **Proof of Lemma**
    390 
    391 We can prove this using a monovariant on the sum of all values in $c$.
    392 
    393 Start with an optimal choice of $c$. If there does not exist an $i$ with $\lvert d[i]\rvert \geq k$, we are done.
    394 
    395 Otherwise, choose one such $i$. Without loss of generality, we can assume $d[i]$ is positive, as the problem is symmetrical when flipped horizontally.
    396 
    397 Now, decrease $c[i+1]$ by $k$. This decreases $d[i]$ by $k$ to a still-positive value, which decreases $\mathrm{throws}$ by $k$. This also increases $d[i+1]$ by $k$, which increases $\mathrm{throws}$ by **at most** $k$. Thus, $\mathrm{throws}$ does not increase, so the new $c$ is still optimal.
    398 
    399 We can apply this operation repeatedly on any optimal solution until we do not have any more differences with absolute value $\geq k$. Since each operation decreases the sum of values in $c$ by $k$, this algorithm terminates since the sum of values in $c$ is finite.
    400 
    401 By the previous lemma, if we have determined $c[i]$, there are at most $2$ choices for $c[i+1]$. (There is $1$ choice when $b[i] = b[i+1]$, resulting in $d[i] = 0$, $c[i] = c[i+1]$, effectively merging the two octopuses.)
    402 
    403 We can visualize this as a DAG in the 2D plane over all points $(i,c[i])$ (over all possible choices of $c[i]$). Each point points to the points in the next column that are the closest above and below (if it exists), forming a grid-like shape. Our goal is to find a path of minimum cost from $(0,0)$ to $(n+1,0)$.
    404 
    405 This is the DAG for the second testcase in samples: ![ ](/predownloaded/4a/57/4a5725cd432bde454f5fb44ed152f26ecba8c618.png)
    406 
    407 Call each time we choose a $c[i+1] \gt c[i]$ (i.e. positive $d[i]$) an *ascent*. Note that the number of ascents is fixed because each nonzero $d[i]$ is either $x$ or $x+k$ for some fixed negative $x$, and there must be a fixed number of $+k$'s to make the total change from $c[0]$ to $c[n+1]$ zero.
    408 
    409 Each ascent brings the path up to the next "row" of descents. Since these rows slope downwards, the $j$th ascent must take place at or before some index $i_j$, because otherwise $c[i_j+1]$ would be negative.
    410 
    411 We can use the following strategy to find a path which we claim is optimal:
    412 
    413 If we can descend, then we descend. Otherwise, either we ascend, or alternatively, we change a previous descent into an ascent so we can descend here. (This can be further simplified by having a hypothetical "descent" here, so you do not need to compare two possibilities in the implementation.) Now, the best such location for an ascent is the one with **minimum cost.**
    414 
    415 **Proof**
    416 
    417 We show how to improve (or preserve the optimality of) any other path into the one chosen by this strategy. Index the ascents by the order they are chosen by the strategy, not in left-to-right order.
    418 
    419 Let $j$ be the index of first ascent this strategy chooses that is not in the compared path. Besides the $j-1$ matching ascents, the compared path must contain at least $1$ more ascent at or before $i_j$, and because of how the strategy chooses ascents, said ascent(s) must have cost no less than the strategy’s $j$th ascent. Any can be changed to match the strategy, since the matching ascents already guarantee that each of the first $j-1$ ascents in left-to-right order happens early enough.
    420 
    421 Repeating the above operation will obtain the strategy’s path.
    422 
    423 We can implement the above strategy with a priority queue, where for each descent we push on the cost of the corresponding ascent, and when an ascent is required, we then pop off the minimum element. In particular, if $b[i] \lt b[i+1]$, then the corresponding ascent has cost $b[i+1]-b[i]$, while if $b[i] \gt b[i+1]$, it has cost $b[i+1]-b[i]+k$. Also, since the bottom of the DAG corresponds to $c[i] = b[i]$, an ascent is required exactly when $b[i] \lt b[i+1]$.
    424 
    425 **Code (C++)**
    426 
    427 ```
    428 #include <bits/stdc++.h>
    429 using namespace std;
    430 typedef long long ll;
    431 
    432 void solve() {
    433 	int n, k;
    434 	cin >> n >> k;
    435 	priority_queue<int, vector<int>, greater<int>> differences;
    436 	int previous = 0;
    437 	ll ans = 0;
    438 	for (int i = 0; i < n; i++) {
    439 		int x;
    440 		cin >> x;
    441 		x %= k;
    442 		if (x > previous) {
    443 			differences.push(x - previous);
    444 			ans += differences.top();
    445   			differences.pop();
    446 		} else {
    447   			differences.push(k + x - previous);
    448 		}
    449 		previous = x;
    450   	}
    451   	cout << ans << "\n";
    452 }
    453 
    454 int main() {
    455 	int t;
    456 	cin >> t;
    457 	while (t--)
    458 		solve();
    459 }
    460 ```
    461 
    462 #### [1852D - Miriany and Matchstick](/contest/1852/problem/D "Codeforces Round 887 (Div. 1)")
    463 
    464 Problem Credits: [ArielShehter](/profile/ArielShehter "Newbie ArielShehter")
    465 
    466 Analysis: [EmeraldBlock](/profile/EmeraldBlock "International Master EmeraldBlock"), [emorgan](/profile/emorgan "International Grandmaster emorgan")
    467 
    468 **Hint 1**
    469 
    470 Solve the samples for all values of $k$.
    471 
    472 **Hint 2**
    473 
    474 What does constructing a second row from left to right look like?
    475 
    476 **Hint 3**
    477 
    478 How does knowing the possible $k$ for any first row help you construct a second row?
    479 
    480 **Hint 4**
    481 
    482 Apply dynamic programming to calculate the possible $k$, and use the information in the DP to construct a solution.
    483 
    484 **Solution**
    485 
    486 Call the number of adjacent pairs of cells with different characters the *cost*.
    487 
    488 If we construct the second row from left to right, the amount each character adds to the cost only depends on the previous character. Thus, we can represent the problem with a DAG whose vertices represent choices for each character and whose edges represent the cost of choosing two adjacent characters. Our goal is to find a path starting from the far left and ending at the far right of cost $k$. For example, below is the DAG for the third testcase in the sample. (For convenience, we include the cost of cells in the top row with the corresponding cells in the bottom row.)
    489 
    490 ![ ](/predownloaded/8c/68/8c6861fe4f76595c811ba4a1182b66420290a9d3.png)
    491 
    492 A general way to find such a path is as follows: For each vertex, store all possible costs of a path starting from the far left and ending at that vertex, which can be calculated with dynamic programming. Then we construct our path backwards from the right. For each candidate previous vertex, we check that the constructed path's cost plus the cost of the edge from this vertex plus some stored cost in this vertex equals $k$, in which case we know that some completion of the path from the far left to this vertex exists and we can choose this vertex.
    493 
    494 Naively calculating this DP would require $O(n)$ time per operation. However, intuitively, each set of possible costs should contain almost all values between its minimum and maximum, and experiments suggest it always consists of at most two intervals. We will first formalize the DP and then prove this observation.
    495 
    496 Let $\mathrm{dp}_A[i]$ store the set of possible values of $k$ when the grid is truncated to the first $i$ columns and the last character in the second row is $A$. Define $\mathrm{dp}_B[i]$ similarly.
    497 
    498 Using the notation $[\mathrm{true}] = 1$, $[\mathrm{false}] = 0$, $S+x = \{s+x \mid s \in S\}$, we have the recurrences
    499 
    500 $\begin{align*} \mathrm{dp}_A[i] &= \mathrm{dp}_A[i-1]\cup(\mathrm{dp}_B[i-1]+1)+[s_i \ne A]+[s_i \ne s_{i-1}] \\ \mathrm{dp}_B[i] &= \mathrm{dp}_B[i-1]\cup(\mathrm{dp}_A[i-1]+1)+[s_i \ne B]+[s_i \ne s_{i-1}] \end{align*}$
    501 
    502 with initial values $\mathrm{dp}_A[1] = [s_1 \ne A]$ and $\mathrm{dp}_B[1] = [s_1 \ne B]$.
    503 
    504 Now either we hope that each set consists of $O(1)$ intervals, or we have to prove that each set indeed consists of at most two intervals:
    505 
    506 **Proof**
    507 
    508 We will use induction to prove that the following stronger property holds for all $i \ge 2$: $\mathrm{dp}_A[i]$ and $\mathrm{dp}_B[i]$ are overlapping intervals, except that possibly one (non-endpoint) value $v$ is missing from one interval, but in that case either $v-1$ or $v+1$ is present in the other interval. ($i = 1$ must be treated separately, but it can easily be checked.)
    509 
    510 **Base case.** To prove this holds for $i = 2$, WLOG let $s_1 = A$ so $\mathrm{dp}_A[1] = \{0\}$ and $\mathrm{dp}_B[1] = \{1\}$. If $s_2 = A$, then
    511 
    512 $\begin{align*} \mathrm{dp}_A[2] &= \{0\}\cup(\{1\}+1)+0+0 = \{0,2\} \\ \mathrm{dp}_B[2] &= \{1\}\cup(\{0\}+1)+1+0 = \{2\} \end{align*}$
    513 
    514 which satisfies the property with $v = 1$. If $s_2 = B$, then
    515 
    516 $\begin{align*} \mathrm{dp}_A[2] &= \{0\}\cup(\{1\}+1)+1+1 = \{2,4\} \\ \mathrm{dp}_B[2] &= \{1\}\cup(\{0\}+1)+0+1 = \{2\} \end{align*}$
    517 
    518 which satisfies the property with $v = 3$.
    519 
    520 **Induction step.** Suppose the property holds for $i-1$.
    521 
    522 Since the conditions of the property only depend on relative positions, for convenience we shift the sets $\mathrm{dp}_A[i]$ and $\mathrm{dp}_B[i]$ left by $h = [s_i \ne A]+[s_i \ne s_{i-1}]$ to get
    523 
    524 $\begin{align*} \mathrm{dp}'_A[i] &= \mathrm{dp}_A[i]-h = \mathrm{dp}_A[i-1]\cup(\mathrm{dp}_B[i-1]+1) \\ \mathrm{dp}'_B[i] &= \mathrm{dp}_B[i]-h = \mathrm{dp}_B[i-1]\cup(\mathrm{dp}_A[i-1]+1)+(s_i = A\ ?\ 1 : -1). \end{align*}$
    525 
    526 If the property holds for $\mathrm{dp}'$, then it holds for $\mathrm{dp}$.
    527 
    528 First, we show that a missing value in $\mathrm{dp}'_A[i]$ or $\mathrm{dp}'_B[i]$ can only come directly from a missing value in $\mathrm{dp}_A[i-1]$ or $\mathrm{dp}_B[i-1]$ and not from the union operation merging two non-adjacent intervals. This is true because $\mathrm{dp}_A[i-1]$ and $\mathrm{dp}_B[i-1]$ overlap, so even after $1$ is added to either, they are still at least adjacent.
    529 
    530 If a value $v$ is missing, WLOG let it be missing from $\mathrm{dp}_A[i-1]$.
    531 
    532 * If $v+1 \in \mathrm{dp}_B[i-1]$, then $\mathrm{dp}'_A[i]$ may be missing $v$ while $\mathrm{dp}'_B[i]$ does not miss any value. Also, since $v-1$ is adjacent to the missing value (which isn't an endpoint), it is in $\mathrm{dp}_A[i-1]$, so either $v+1$ or $v-1$ is in $\mathrm{dp}'_B[i]$. This also guarantees the intervals overlap, satisfying the property for $i$.
    533 * The case for $v-1 \in \mathrm{dp}_B[i-1]$ is very similar. $\mathrm{dp}'_B[i]$ may be missing either $v$ or $v+2$, and since $v+1 \in \mathrm{dp}_A[i-1]$, $v+1$ is in $\mathrm{dp}'_A[i]$.
    534 
    535 If no value is missing, let $x$ be a common value in both $\mathrm{dp}_A[i-1]$ and $\mathrm{dp}_B[i-1]$. Then, $\mathrm{dp}'_A[i] \supseteq \{x,x+1\}$ and $\mathrm{dp}'_B[i]$ is a superset of either $\{x-1,x\}$ or $\{x+1,x+2\}$, so the intervals overlap.
    536 
    537 To find the union of two sets of intervals, sort them by left endpoint and merge adjacent overlapping intervals. After computing the DP, apply the aforementioned backwards construction to obtain a valid second row.
    538 
    539 Below is a visualization of solving the third testcase in the sample. Generate your own [here](https://artofproblemsolving.com/texer/codeforces)!
    540 
    541 ![ ](/predownloaded/95/e5/95e5e2909095d886213e4d21b68c42867318f72d.png)
    542 
    543 **Code (C++)**
    544 
    545 ```
    546 #include <bits/stdc++.h>
    547 using namespace std;
    548 
    549 #define all(x) (x).begin(), (x).end()
    550 
    551 struct state {
    552 
    553     // represents a set of integers compressed as a vector
    554     // of non-overlapping intervals [l, r]
    555 
    556     basic_string<array<int, 2>> a;
    557 
    558     // add d to everything in the set
    559     friend state add(state x, int d) {
    560         for (auto& [l, r] : x.a)
    561             l += d, r += d;
    562         return x;
    563     }
    564 
    565     // union of two sets of integers
    566     friend state unite(state x, state y) {
    567         state z;
    568         merge(all(x.a), all(y.a), back_inserter(z.a));
    569         int j = 0;
    570         for (int i = 1; i < z.a.size(); i++) {
    571             if (z.a[i][0] <= z.a[j][1]+1)
    572                 z.a[j][1] = max(z.a[j][1], z.a[i][1]);
    573             else
    574                 z.a[++j] = z.a[i];
    575         }
    576         z.a.erase(z.a.begin() + j + 1, z.a.end());
    577         return z;
    578     }
    579 
    580     // whether integer k is in the set
    581     friend bool contains(state x, int k) {
    582         for (auto& [l, r] : x.a)
    583             if (k >= l && k <= r)
    584                 return true;
    585         return false;
    586     }
    587 };
    588 
    589 // set containing only one integer d
    590 state from_constant(int d) {
    591     return state({{{d, d}}});
    592 }
    593 
    594 int main() {
    595     ios_base::sync_with_stdio(0); cin.tie(0);
    596     int t; cin >> t;
    597     while (t--) {
    598         int n, k; cin >> n >> k;
    599         string s; cin >> s;
    600 
    601         vector<array<state, 2>> dp(n);
    602 
    603         dp[0][0] = from_constant(s[0] != 'A');
    604         dp[0][1] = from_constant(s[0] != 'B');
    605 
    606         for (int i = 1; i < n; i++) {
    607             dp[i][0] = add(unite(dp[i-1][0], add(dp[i-1][1], 1)), (s[i] != 'A') + (s[i] != s[i-1]));
    608             dp[i][1] = add(unite(dp[i-1][1], add(dp[i-1][0], 1)), (s[i] != 'B') + (s[i] != s[i-1]));
    609         }
    610 
    611         if (!(contains(dp[n-1][0], k) || contains(dp[n-1][1], k))) {
    612             cout << "NO\n";
    613             continue;
    614         }
    615 
    616         string ans;
    617 
    618         for (int i = n-1; i >= 0; i--) {
    619             char c = contains(dp[i][0], k - (i == n-1 ? 0 : (ans.back() != 'A'))) ? 'A' : 'B';
    620             k -= (c != s[i]);
    621             if (i > 0)
    622                 k -= (s[i] != s[i-1]);
    623             if (i < n-1)
    624                 k -= (c != ans.back());
    625             ans += c;
    626         }
    627 
    628         reverse(all(ans));
    629         cout << "YES\n" << ans << "\n";
    630     }
    631 }
    632 ```
    633 
    634 #### [1852E - Rivalries](/contest/1852/problem/E "Codeforces Round 887 (Div. 1)")
    635 
    636 Problem Credits: [buffering](/profile/buffering "Expert buffering"), [ArielShehter](/profile/ArielShehter "Newbie ArielShehter"), [fast-fourier-transfem](/profile/fast-fourier-transfem "Candidate Master fast-fourier-transfem")
    637 
    638 Analysis: [oursaco](/profile/oursaco "Master oursaco")
    639 
    640 **Hint 1**
    641 
    642 For each distinct value, only the leftmost and rightmost positions actually have an effect on the power.
    643 
    644 **Hint 2**
    645 
    646 Think of each distinct value as an interval corresponding to its leftmost and rightmost positions, and let that distinct value be the value of its interval. If interval $x$ strictly contains an interval $y$ with greater value, then $x$ will not have an effect on the power and it can be discarded.
    647 
    648 **Hint 3**
    649 
    650 In order to not change the power, we can only add intervals that strictly contain an interval with greater value. Afterwards, if $i$ is not the endpoint of an interval, $b_i$ equals the largest value of an interval containing $i$.
    651 
    652 **Hint 4**
    653 
    654 There will only be at most one interval that we have to add. Assume that there are multiple intervals that we can add without changing the answer. In this case it is easy to see that its more optimal to combine the interval with smaller value into the interval with larger value. Thus, it is never optimal to add multiple intervals.
    655 
    656 **Solution**
    657 
    658 Read the hints.
    659 
    660 We can remove all intervals that will not affect the power by iterating over them in decreasing order of value and maintain a segment tree that stores for each left endpoint of any processed intervals, the right endpoint that corresponds to it. Checking if an interval is strictly contained then becomes a range minimum query.
    661 
    662 Assume that we know the value $x$ of the interval that we want to add. We can immediately fill the value for the interior of all intervals that correspond to a value greater than $x$. However, we also have to guarantee that $x$ is strictly contained by an interval with greater value, so we can try each interval to contain $x$. If are no unfilled indices the left or right side of the interval, then we want to replace the smallest filled on either side value with $x$. Otherwise, we can just fill in all the unfilled indices with $x$. Note that it is also possible for $x$ to not be able to be contained by any interval.
    663 
    664 Thus, we can just try every possible $x$ in decreasing order and maintain the filled indices as we iterate. There are only at most $n$ values of $x$ to check, which is just the set of $a_i - 1$ that does not appear in $a$.
    665 
    666 **Code (C++)**
    667 
    668 ```
    669 #include <bits/stdc++.h>
    670 using namespace std;
    671 
    672 #define pb push_back
    673 #define ff first
    674 #define ss second
    675 
    676 typedef long long ll;
    677 typedef pair<int, int> pii;
    678 typedef pair<ll, ll> pll;
    679 
    680 const int INF = 1e9 + 1;
    681 
    682 void setIO() {
    683     ios_base::sync_with_stdio(0); cin.tie(0);
    684 }
    685 
    686 pii seg[400005];
    687 int n;
    688 
    689 void build(int l = 0, int r = n - 1, int cur = 0){
    690     seg[cur] = {INF, INF};
    691     if(l == r) return;
    692     int mid = (l + r)/2;
    693     build(l, mid, cur*2 + 1);
    694     build(mid + 1, r, cur*2 + 2);
    695 }
    696 
    697 void update(int x, int v, int l = 0, int r = n - 1, int cur = 0){
    698     if(l == r){
    699         seg[cur] = {v, l};
    700         return;
    701     }
    702     int mid = (l + r)/2;
    703     if(x <= mid) update(x, v, l, mid, cur*2 + 1);
    704     else update(x, v, mid + 1, r, cur*2 + 2);
    705     seg[cur] = min(seg[cur*2 + 1], seg[cur*2 + 2]);
    706 }
    707 
    708 pii query(int l, int r, int ul = 0, int ur = n - 1, int cur = 0){
    709     if(l <= ul && ur <= r) return seg[cur];
    710     if(l > r || ur < l || ul > r) return {INF, INF};
    711     int mid = (ul + ur)/2;
    712     return min(query(l, r, ul, mid, cur*2 + 1), query(l, r, mid + 1, ur, cur*2 + 2));
    713 }
    714 
    715 int main(){
    716     setIO();
    717     int t;
    718     cin >> t;
    719     for(int tt = 1; tt <= t; tt++){
    720         cin >> n;
    721         map<int, vector<int>> m;
    722         int arr[n];
    723         for(int i = 0; i < n; i++){
    724             cin >> arr[i];
    725             m[arr[i]].pb(i);
    726         }
    727         vector<int> rel; //relevant numbers
    728         for(auto &i : m){
    729             rel.pb(i.ff);
    730             for(int j = 1; j < i.ss.size() - 1; j++){
    731                 arr[i.ss[j]] = 0;
    732             }
    733         }
    734         reverse(rel.begin(), rel.end());
    735         vector<int> nw;
    736         build();
    737         for(int i : rel){
    738             int l = m[i].front(), r = m[i].back();
    739             if(query(l, r).ff <= r){
    740                 arr[l] = arr[r] = 0;
    741             } else {
    742                 update(l, r);
    743                 nw.pb(i);
    744             }
    745         }
    746         swap(rel, nw);
    747         set<int> s;
    748         for(int i = 0; i < n; i++) if(!arr[i]) s.insert(i);
    749         vector<int> vals; //possible target values
    750         for(int i = rel.size() - 1; i >= 0; i--){
    751             if(i == rel.size() - 1 || rel[i] - 1 != rel[i + 1]){
    752                 vals.pb(rel[i] - 1);
    753             }
    754         }
    755         ll sum = 0, mx = 0, mxval = 0;
    756         int lex = -1, rex = -1;
    757         build();
    758         for(int i = 0; i < n; i++) if(!arr[i]) update(i, -1);
    759         reverse(vals.begin(), vals.end());
    760         queue<pii> upd;
    761         int ind = 0;
    762         //try to add an interval with value i
    763         for(int i : vals){
    764             vector<int> nxt;
    765             //try filling in all intervals > i
    766             while(ind < rel.size() && rel[ind] > i){
    767                 int l = m[rel[ind]].front(), r = m[rel[ind]].back();
    768                 set<int>::iterator it = s.lower_bound(l);
    769                 while(it != s.end() && *it < r){
    770                     sum += rel[ind];
    771                     update(*it, rel[ind]);
    772                     upd.push({*it, rel[ind]});
    773                     it = s.erase(it);
    774                 }
    775                 nxt.pb(rel[ind++]);
    776             }
    777             //try each necessary interval to be strictly contained by i
    778             for(int j : nxt){
    779                 int l = m[j].front(), r = m[j].back();
    780                 if(s.size() && 0 < l && r < n - 1){
    781                     //find which indeces on each side to replace with i
    782                     pii rnw = query(r + 1, n);
    783                     pii lnw = query(0, l - 1);
    784                     if(rnw.ff == INF || lnw.ff == INF) continue;
    785                     ll add = (ll)i*s.size() + (rnw.ff == -1 ? 0 : i - rnw.ff) + (lnw.ff == -1 ? 0 : i - lnw.ff);
    786                     if(i && sum + add > mx){
    787                         mx = sum + add;
    788                         mxval = i;
    789                         lex = (lnw.ff == -1 ? -1 : lnw.ss);
    790                         rex = (rnw.ff == -1 ? -1 : rnw.ss);
    791                         //it is optimal to fill in all intervals > i
    792                         while(!upd.empty()){
    793                             arr[upd.front().ff] = upd.front().ss;
    794                             upd.pop();
    795                         }
    796                     }
    797                 }
    798             }
    799         }
    800         //don't want to add any intervals
    801         if(s.size() == 0 && sum > mx){
    802             mx = sum;
    803             lex = rex = -1;
    804             //it is optimal to fill in all remaining intervals
    805             while(!upd.empty()){
    806                 arr[upd.front().ff] = upd.front().ss;
    807                 upd.pop();
    808             }
    809         }
    810         if(lex != -1) arr[lex] = 0;
    811         if(rex != -1) arr[rex] = 0;
    812         for(int i = 0; i < n; i++) cout << (arr[i] ? arr[i] : mxval) << " ";
    813         cout << endl;
    814     }
    815 }
    816 ```
    817 
    818 #### [1852F - Panda Meetups](/contest/1852/problem/F "Codeforces Round 887 (Div. 1)")
    819 
    820 Problem Credits: [Benq](/profile/Benq "Legendary Grandmaster Benq")
    821 
    822 Analysis: [Benq](/profile/Benq "Legendary Grandmaster Benq"), [oursaco](/profile/oursaco "Master oursaco")
    823 
    824 **Hint 1**
    825 
    826 If we want to answer one of the questions (say, the question involving all the events) in polynomial time, how do we do it?
    827 
    828 **Hint 2**
    829 
    830 Construct a network with edges from the source to each of the red panda events with capacities equal to the number of red pandas, edges from red panda events to blue panda events with innite capacities if the red pandas can catch the corresponding blue pandas, and edges from each of the blue panda events to the sink with capacities equal to the number of blue pandas.
    831 
    832 **Hint 3**
    833 
    834 The next step is to use the max-flow min-cut theorem: the maximum flow is equal to the minimum number of red pandas plus blue pandas we need to remove from the graph such that no remaining red panda can reach any remaining blue panda.
    835 
    836 How do we go from here?
    837 
    838 **Hint 4**
    839 
    840 For any cut, consider the region of the $x$-$t$ plane reachable by the remaining red pandas. No remaining blue pandas can lie in this region, and its border is a polyline that intersects each vertical line in the $x$-$t$ plane exactly once. Furthermore, the slope of every segment in this polyline has slope plus or minus $1$. Conversely, we can associate every polyline satisfying this condition with a cut; we just need to remove every red panda lying below the polyline and every blue panda lying on or above the polyline.
    841 
    842 Now, figure out how to answer the queries online.
    843 
    844 **Solution**
    845 
    846 Read the hints to understand the solution better.
    847 
    848 We can answer the queries online. For each $x$-coordinate $x$, maintain a treap that stores for every $x$-coordinate, the minimum cut $dp[x][t]$ associated with a polyline satisfying the condition above that starts at $x = -\infty$ and ends at $(x, t)$ when only considering events with $x$-coordinate at most $x$. When transitioning from to $x$ to $x+1$, we need to set for every $dp[x+1][t] = min(dp[x][t-1], dp[x][t], dp[x][t+1])$ for every $t$. To do this quickly, we maintain the values of $t$ where $dp[x][t+1] - dp[x][t] \neq 0$ in increasing order, of which there are at most $n$. When $x$ increases by one, each value of increases or decreases by one, depending on the sign of $dp[x][t+1]-dp[x][t]$, and some of the values of $t$ merge, decreasing the size of our treap. As long as we can process each merge in $\log n$ time, our solution will run in $O(n\log n)$ total time. When processing an event, we need to increase all $dp$ values in a suffix for red panda events, and all $dp$ values in a prefix for blue panda events. To answer a query, we just need to return the minimum prefix sum in our treap.
    849 
    850 **Code (C++)**
    851 
    852 ```
    853 #include <bits/stdc++.h>
    854 using namespace std;
    855 
    856 #define pb push_back
    857 #define ff first
    858 #define ss second
    859 
    860 typedef long long ll;
    861 typedef pair<int, int> pii;
    862 typedef pair<ll, ll> pll;
    863 
    864 const int INF = 1e9 + 1;
    865 
    866 void setIO() {
    867     ios_base::sync_with_stdio(0); cin.tie(0);
    868 }
    869 
    870 struct node {
    871     //mnpos - leftmost negative 
    872     //mxpos - rightmost positive
    873     int pos, tag, mnpos, mxpos;
    874     //minimum distance
    875     pair<int, pii> mndif;
    876     ll sum, pre, val;
    877     int weight;
    878 
    879     node(){}
    880 
    881     node(int pos_, ll val_){
    882         pos = pos_;
    883         val = val_;
    884         sum = val;
    885         pre = min((ll)0, val);
    886         mxpos = -INF;
    887         mnpos = INF;
    888         mndif = {INF, {INF, INF}};
    889         if(val > 0) mxpos = pos;
    890         if(val < 0) mnpos = pos;
    891         tag = 0;
    892         weight = rand();
    893     }
    894 };
    895 
    896 int sz = 1;
    897 node treap[1000005];
    898 int left0[1000005];
    899 int right0[1000005];
    900 
    901 int newnode(int pos, ll val){
    902     treap[sz] = node(pos, val);
    903     return sz++;
    904 }
    905 
    906 pair<int, pii> comb(int a, int b){
    907     if(a == -INF || b == INF) return {INF, {INF, INF}};
    908     return {b - a, {a, b}};
    909 }
    910 
    911 void pull(int x){
    912     treap[x].sum = treap[x].val;
    913     treap[x].pre = min((ll)0, treap[x].val);
    914     treap[x].mxpos = -INF;
    915     treap[x].mnpos = INF;
    916     treap[x].mndif = {INF, {INF, INF}};
    917     if(treap[x].val > 0) treap[x].mxpos = treap[x].pos;
    918     if(treap[x].val < 0) treap[x].mnpos = treap[x].pos;
    919     if(left0[x]){
    920         treap[x].mndif = min(treap[x].mndif, treap[left0[x]].mndif);
    921         treap[x].mndif = min(treap[x].mndif, comb(treap[left0[x]].mxpos, treap[x].mnpos));
    922         treap[x].mnpos = min(treap[x].mnpos, treap[left0[x]].mnpos);
    923         treap[x].mxpos = max(treap[x].mxpos, treap[left0[x]].mxpos);
    924         treap[x].pre = min(treap[left0[x]].pre, treap[left0[x]].sum + treap[x].pre);
    925         treap[x].sum += treap[left0[x]].sum; 
    926     }
    927     if(right0[x]){
    928         treap[x].mndif = min(treap[x].mndif, treap[right0[x]].mndif);
    929         treap[x].mndif = min(treap[x].mndif, comb(treap[x].mxpos, treap[right0[x]].mnpos));
    930         treap[x].mnpos = min(treap[x].mnpos, treap[right0[x]].mnpos);
    931         treap[x].mxpos = max(treap[x].mxpos, treap[right0[x]].mxpos);
    932         treap[x].pre = min(treap[x].pre, treap[x].sum + treap[right0[x]].pre);
    933         treap[x].sum += treap[right0[x]].sum;
    934     }
    935 }
    936 
    937 int move(node& x, int shift){
    938     int ret = x.pos;
    939     if(x.val < 0) ret -= shift;
    940     if(x.val > 0) ret += shift;
    941     return ret;
    942 }
    943 
    944 void apply(int x, int tag){
    945     treap[x].pos = move(treap[x], tag);
    946     treap[x].tag += tag;
    947     if(treap[x].mnpos != INF) treap[x].mnpos -= tag;
    948     if(treap[x].mxpos != -INF) treap[x].mxpos += tag;
    949     if(treap[x].mndif.ff != INF){
    950         treap[x].mndif.ff -= 2*tag;
    951         treap[x].mndif.ss.ff += tag;
    952         treap[x].mndif.ss.ss -= tag;
    953     }
    954 }
    955 
    956 void push(int x){
    957     if(!treap[x].tag) return;
    958     if(left0[x]) apply(left0[x], treap[x].tag);
    959     if(right0[x]) apply(right0[x], treap[x].tag);
    960     treap[x].tag = 0;
    961 }
    962 
    963 int merge(int a, int b){
    964     if(!a) return b;
    965     if(!b) return a;
    966     if(treap[a].weight < treap[b].weight){ 
    967         push(a);
    968         right0[a] = merge(right0[a], b);
    969         pull(a);
    970         return a;
    971     } else {
    972         push(b);
    973         left0[b] = merge(a, left0[b]);
    974         pull(b);
    975         return b;
    976     }
    977 }
    978 
    979 //splits rt's tree into [0, k) [k, INF)
    980 pair<int, int> split(int x, int k){
    981     if(!x) return pair<int, int>{0, 0};
    982     push(x);
    983     pair<int, int> ret;
    984     if(treap[x].pos < k){
    985         ret = split(right0[x], k);
    986         right0[x] = ret.first;
    987         ret.first = x;
    988     } else {
    989         ret = split(left0[x], k);
    990         left0[x] = ret.second;
    991         ret.second = x;
    992     }
    993     pull(x);
    994     return ret;
    995 }
    996 
    997 int rt = 0;
    998 
    999 void erase(int x){
   1000     pair<int, int> a = split(rt, x);
   1001     pair<int, int> b = split(a.second, x + 1);
   1002     rt = merge(a.first, b.second);
   1003 }
   1004 
   1005 //position, value
   1006 void insert(int a, ll b){
   1007     if(!rt){
   1008         rt = newnode(a, b);
   1009         return;
   1010     }
   1011     pair<int, int> nw = split(rt, a);
   1012     rt = merge(nw.first, merge(newnode(a, b), nw.second));
   1013 }
   1014 
   1015 //value
   1016 ll query(int x){
   1017     pair<int, int> a = split(rt, x);
   1018     pair<int, int> b = split(a.second, x + 1); 
   1019     ll ret = (b.first ? treap[b.first].val : 0);
   1020     rt = merge(a.first, merge(b.first, b.second));
   1021     return ret;
   1022 }
   1023 
   1024 int main(){
   1025     setIO();
   1026     int n;
   1027     cin >> n;
   1028     int prv = 0;
   1029     ll st = 0;
   1030     for(int i = 1; i <= n; i++){
   1031         int x, t, c;
   1032         cin >> x >> t >> c;
   1033         int dif = x - prv;
   1034         //remove overlap
   1035         while(rt && treap[rt].mndif.ff <= 2*dif){
   1036             pair<int, pii> x = treap[rt].mndif;
   1037             ll a = query(x.ss.ff), b = query(x.ss.ss);
   1038             ll sub = min(a, -b);
   1039             erase(x.ss.ff);
   1040             erase(x.ss.ss);
   1041             a -= sub, b += sub;
   1042             if(a != 0) insert(x.ss.ff, a);
   1043             if(b != 0) insert(x.ss.ss, b);
   1044         }
   1045         //shift everything
   1046         if(rt){
   1047             treap[rt].pos = move(treap[rt], dif);
   1048             treap[rt].tag += dif;
   1049             if(treap[rt].mnpos != INF) treap[rt].mnpos -= dif;
   1050             if(treap[rt].mxpos != -INF) treap[rt].mxpos += dif;
   1051             if(treap[rt].mndif.ff != INF){
   1052                 treap[rt].mndif.ff -= 2*dif;
   1053                 treap[rt].mndif.ss.ff += dif;
   1054                 treap[rt].mndif.ss.ss -= dif;
   1055             }
   1056         }
   1057         ll cur = query(t + 1);
   1058         if(cur != 0) erase(t + 1);
   1059         if(cur - c != 0) insert(t + 1, cur - c);
   1060         if(c > 0) st += c;
   1061         cout << st + (!rt ? 0 : treap[rt].pre) << endl;
   1062         prv = x;
   1063     }
   1064 }
   1065 ```