codeforces-scrape

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

2234.md (19919B)


      1 Source: https://codeforces.com/blog/entry/154319
      2 
      3 Thank you for participating in our round! We hope you enjoyed the problems.
      4 
      5 [2234A - Euclid, Sequence and Two Numbers](/contest/2234/problem/A "Codeforces Round 1102 (Div. 2)")
      6 
      7 Idea: [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx")
      8 
      9 **Hint 1**
     10 
     11 Note that $(a_i \bmod a_{i + 1}) \lt a_{i + 1}$.
     12 
     13 **Hint 2**
     14 
     15 $a_{i + 2} = (a_i \bmod a_{i + 1}) \lt a_{i + 1}$ and $a_2 \le a_1$ mean that the sequence $a$ must be non-increasing. On the other hand, there is only one permutation of the sequence $b$ that can be non-increasing.
     16 
     17 **Solution**
     18 
     19 Tutorial is loading...
     20 
     21 **Code (Python)**
     22 
     23 ```
     24 t = int(input())
     25 for tt in range(t):
     26     n = int(input())
     27     a = list(map(int, input().split()))
     28     a.sort()
     29     a = a[::-1]
     30     valid = True
     31     for i in range(2, n):
     32         if a[i] != a[i - 2] % a[i - 1]:
     33             print(-1)
     34             valid = False
     35             break
     36     if valid:
     37         print(a[0], a[1])
     38 ```
     39 
     40 **Code (C++)**
     41 
     42 ```
     43 #include <iostream>
     44 #include <vector>
     45 #include <algorithm>
     46 
     47 using namespace std;
     48 
     49 void solve() {
     50     int n;
     51     cin >> n;
     52     vector<int> b(n);
     53     for (int i = 0; i < n; i++) {
     54         cin >> b[i];
     55     }
     56     sort(b.rbegin(), b.rend());
     57     bool ok = true;
     58     for (int i = 0; i < n - 2; i++) {
     59         if (b[i + 2] != b[i] % b[i + 1]) {
     60             ok = false;
     61             break;
     62         }
     63     }
     64     if (ok) {
     65         cout << b[0] << " " << b[1] << "\n";
     66     } else {
     67         cout << -1 << "\n";
     68     }
     69 }
     70 
     71 int main() {
     72     int t;
     73     cin >> t;
     74     
     75     while (t--) {
     76         solve();
     77     }
     78 }
     79 ```
     80 
     81 **Rate the problem**
     82 
     83 Amazing
     84 
     85 Good
     86 
     87 Ok
     88 
     89 Bad
     90 
     91 Terrible
     92 
     93 [2234B - Palindrome, Twelve and Two Terms](/contest/2234/problem/B "Codeforces Round 1102 (Div. 2)")
     94 
     95 Idea: [Fakewave](/profile/Fakewave "Master Fakewave")
     96 
     97 **Solution**
     98 
     99 Tutorial is loading...
    100 
    101 **Code (Python)**
    102 
    103 ```
    104 tt = int(input())
    105 for tc in range(tt):
    106     n = int(input())
    107     if n == 10:
    108         print(-1)
    109     elif n % 12 == 10:
    110         print(22, n - 22)
    111     else:
    112         print(n % 12, n - (n % 12))
    113 ```
    114 
    115 **Code (C++)**
    116 
    117 ```
    118 #include <bits/stdc++.h>
    119  
    120 using namespace std;
    121  
    122 void solve() {
    123     long long n;
    124     cin >> n;
    125     if (n == 10) {
    126         cout << "-1\n";
    127     } else if (n % 12 == 10) {
    128         cout << "22 " << n - 22 << "\n";
    129     } else {
    130         cout << n % 12 << " " << n - (n % 12) << "\n";
    131     }
    132 }
    133  
    134 int main() {
    135     ios_base::sync_with_stdio(0); cin.tie(0);
    136  
    137     int t;
    138     cin >> t;
    139     while (t--) {
    140         solve();
    141     }
    142 }
    143 ```
    144 
    145 **Rate the problem**
    146 
    147 Amazing
    148 
    149 Good
    150 
    151 Ok
    152 
    153 Bad
    154 
    155 Terrible
    156 
    157 [2234C - Vessels, Heights and Two Versions (Easy Version)](/contest/2234/problem/C "Codeforces Round 1102 (Div. 2)")
    158 
    159 Idea: [yanb0](/profile/yanb0 "Candidate Master yanb0")
    160 
    161 **Hint**
    162 
    163 Intuitively, the farther a vessel from the empty one, the more water there can be. Fix the empty vessel and try to explicitly find the formula for the maximum possible water height in each of the other vessels.
    164 
    165 **Solution**
    166 
    167 Tutorial is loading...
    168 
    169 **Code (Python)**
    170 
    171 ```
    172 t = int(input())
    173 for tc in range(t):
    174     n = int(input())
    175     h = list(map(int, input().split()))
    176     ans = []
    177     for s in range(n):
    178         w1 = [0] * n
    179         w2 = [0] * n
    180         for i in range(1, n):
    181             w1[(s + i) % n] = max(w1[(s + i - 1) % n], h[(s + i - 1) % n])
    182         for i in range(1, n):
    183             w2[(s + n - i) % n] = max(w2[(s + n - i + 1) % n], h[(s + n - i) % n])
    184         w = [min(w1[i], w2[i]) for i in range(n)]
    185         ans.append(sum(w))
    186     print(*ans)
    187 ```
    188 
    189 **Code (C++)**
    190 
    191 ```
    192 #include <bits/stdc++.h>
    193 
    194 using namespace std;
    195  
    196 void solve() {
    197     int n;
    198     cin >> n;
    199     vector<int> h(n);
    200     for (int i = 0; i < n; i++) cin >> h[i];
    201     
    202     for (int s = 0; s < n; s++) {
    203         vector<int> w1(n), w2(n), w(n);
    204         for (int i = 1; i < n; i++) {
    205             w1[(s + i) % n] = max(w1[(s + i - 1) % n], h[(s + i - 1) % n]);
    206         }
    207         for (int i = 1; i < n; i++) {
    208             w2[(s + n - i) % n] = max(w2[(s + n - i + 1) % n], h[(s + n - i) % n]);
    209         }
    210         for (int i = 0; i < n; i++) {
    211             w[i] = min(w1[i], w2[i]);
    212         }
    213         cout << accumulate(w.begin(), w.end(), 0ll) << " ";
    214     }
    215     cout << "\n";
    216 }
    217  
    218 signed main() {
    219     ios_base::sync_with_stdio(0); cin.tie(0);
    220  
    221     int t;
    222     cin >> t;
    223     while (t--) {
    224         solve();
    225     }
    226 }
    227 ```
    228 
    229 **Rate the problem**
    230 
    231 Amazing
    232 
    233 Good
    234 
    235 Ok
    236 
    237 Bad
    238 
    239 Terrible
    240 
    241 [2234D - XOR, Expression and Two Binary Numbers](/contest/2234/problem/D "Codeforces Round 1102 (Div. 2)")
    242 
    243 Idea: [Fakewave](/profile/Fakewave "Master Fakewave")
    244 
    245 **Hint 1.1**
    246 
    247 Let $A = a_1$, $B = a_{2^k + 1}$, $C = A \oplus B$.
    248 
    249 Try to write out some values of $a$, for example, for $k = 3$.
    250 
    251 **Hint 1.2**
    252 
    253 $A \oplus B = C$, $B \oplus C = A$, $C \oplus A = B$.
    254 
    255 **Hint 1.3**
    256 
    257 Let's see how $a$ changes step by step:
    258 
    259 * `a = [A, ?, ?, ?, ?, ?, ?, ?, B]`;
    260 * `a = [A, ?, ?, ?, C, ?, ?, ?, B]`;
    261 * `a = [A, ?, B, ?, C, ?, A, ?, B]`;
    262 * `a = [A, C, B, A, C, B, A, C, B]`.
    263 
    264 Try to notice and prove a pattern.
    265 
    266 **Solution 1**
    267 
    268 Tutorial is loading...
    269 
    270 **Code (C++) of Solution 1**
    271 
    272 ```
    273 #include <bits/stdc++.h>
    274 
    275 using namespace std;
    276 
    277 void solve() {
    278     int n, k;
    279     cin >> n >> k;
    280     vector<int> a(n), b(n);
    281     char g;
    282     for (int i = 0; i < n; ++i) {
    283         cin >> g;
    284         a[i] = g - '0';
    285     }
    286     for (int i = 0; i < n; ++i) {
    287         cin >> g;
    288         b[i] = g - '0';
    289     }
    290     vector<int> c(4);
    291     for (int i = 0; i < n; ++i) {
    292         int x = 2 * a[i] + b[i];
    293         c[x]++;
    294     }
    295         
    296     if (k % 2) {
    297         long long p = 0, q = 0, r = 0;
    298         p = c[0] + c[1];
    299         q = c[0] + c[3];
    300         r = c[0] + c[2];
    301         cout << (((1ll << k) + 1) / 3) * (p * (n-p) + q * (n - q) + r * (n - r)) << "\n";
    302     } else {
    303         long long p = 0, q = 0, r = 0;
    304         p = c[0] + c[1];
    305         q = c[0] + c[2];
    306         r = c[0] + c[3];
    307         cout << (((1ll << k) + 1) / 3) * (p * (n-p) + q * (n - q) + r * (n - r)) + p * (n - p) + q * (n - q) << "\n";
    308     }
    309 }
    310 
    311 signed main() {
    312     ios_base::sync_with_stdio(false);
    313     cin.tie(nullptr);
    314     int t;
    315     cin >> t;
    316     while (t--) {
    317         solve();
    318     }
    319 }
    320 ```
    321 
    322 **Hint 2.1**
    323 
    324 There is a rather straightforward solution that works in $\mathcal{O}(nk \log k)$.
    325 
    326 **Hint 2.2**
    327 
    328 Read the first two hints for Solution 1. Prove that each $a_i \in [A, B, C]$.
    329 
    330 **Hint 2.3**
    331 
    332 For every pair of bits $(x, y)$, count the number of positions $h$ for which the $h$-th bits of $a_1$ and $a_{2^k+1}$ are $x$ and $y$ respectively. Continue recursively.
    333 
    334 **Hint 2.4**
    335 
    336 Use caching.
    337 
    338 **Solution 2**
    339 
    340 Let the answer for the problem where $a_1 = A$, $a_{2^k+1} = B$ and $k = l$ be $F(l, A, B)$.
    341 
    342 Then, as we write a value $A \oplus B$ in the middle of the array on the first step and then continue recursively, like for $k = l - 1$, $F(l, A, B) = F(l - 1, A, A \oplus B) + F(l - 1, A \oplus B, B) - [\text{product of the } 0 \text{ and } 1 \text{ bit counts for } A \oplus B]$.
    343 
    344 Referring to the proof in Solution 1 that each $a_i \in [A, B, C]$, for each $l$ the function's value must be calculated for different pairs of $(A, B)$ at most $6$ times, thus, if we use a map for caching the answer of $F$, we will make not more than $6k$ calls to it, which makes the time complexity $\mathcal{O}(n + k \log k)$.
    345 
    346 **Code (C++) of Solution 2**
    347 
    348 ```
    349 #include <bits/stdc++.h>
    350 
    351 using namespace std;
    352 #define int long long
    353 
    354 int n, k, a, b, c;
    355 string p, q, r;
    356 
    357 int get(string &s) {
    358     int a = 0, b = 0;
    359     for (char c : s)
    360         if (c == '0') a++;
    361         else b++;
    362     return a * b;
    363 }
    364 
    365 map<array<int, 4>, int> mp;
    366 
    367 int solve(int l, int a, int b, int c) {
    368     array<int, 4> t = {l, a, b, c};
    369     if (mp.find(t) == mp.end()) {
    370         if (l == 0) mp[t] = a + b;
    371         else mp[t] = solve(l - 1, c, a, b) + solve(l - 1, b, c, a) - c;
    372     }
    373     return mp[t];
    374 }
    375 
    376 void test_case() {
    377     cin >> n >> k >> p >> q;
    378     r.clear();
    379     for (int i = 0; i < n; i++)
    380         r.push_back('0' + ((p[i] - '0') ^ (q[i] - '0')));
    381     a = get(p);
    382     b = get(q);
    383     c = get(r);
    384     mp.clear();
    385     cout << solve(k, a, b, c) << '\n';
    386 }
    387 
    388 int32_t main() {
    389     ios::sync_with_stdio(0); cin.tie(0);
    390     int t; cin >> t;
    391     while (t--) test_case();
    392 }
    393 ```
    394 
    395 **Rate the problem**
    396 
    397 Amazing
    398 
    399 Good
    400 
    401 Ok
    402 
    403 Bad
    404 
    405 Terrible
    406 
    407 [2234E - Vlad, Misha and Two Arrays](/contest/2234/problem/E "Codeforces Round 1102 (Div. 2)")
    408 
    409 Idea: [Fakewave](/profile/Fakewave "Master Fakewave")
    410 
    411 **Hint 1.1**
    412 
    413 Looking only at the array $a$, how to deduce the index $i$ for which $p_i = 1$, i.e. the minimum of $p$?
    414 
    415 **Hint 1.2**
    416 
    417 Try to come up with a recursive solution that works in $\mathcal{O}(n^2)$.
    418 
    419 **Solution 1 (yanb0)**
    420 
    421 Tutorial is loading...
    422 
    423 **Code (C++)**
    424 
    425 ```
    426 #include <bits/stdc++.h>
    427 
    428 #define int long long
    429 
    430 using namespace std;
    431 
    432 const int Mod = 1e9 + 7, Max = 5e5 + 10;
    433 
    434 vector<int> fact(Max), ifact(Max);
    435 
    436 int binpow(int b, int p) {
    437     if (p == 0) return 1;
    438     if (p % 2 == 0) return binpow((b * b) % Mod, p / 2);
    439     return (binpow(b, p - 1) * b) % Mod;
    440 }
    441 
    442 int C(int n, int k) {
    443     return (fact[n] * ((ifact[k] * ifact[n - k]) % Mod)) % Mod;
    444 }
    445 
    446 int rec(int l, int r, vector<int> &b) {
    447     if (r < l) {
    448         return 1;
    449     }
    450     if (l == r) {
    451         return (b[l] == 1 ? 1 : 0);
    452     }
    453     for (int d = 0; d < r - l + 1; d++) {
    454         int i = d + l;
    455         if ((i - l + 1) * (r - i + 1) == b[i]) {
    456             return (((rec(l, i - 1, b) * rec(i + 1, r, b)) % Mod) * C(r - l, i - l)) % Mod;
    457         }
    458         i = r - d;
    459         if ((i - l + 1) * (r - i + 1) == b[i]) {
    460             return (((rec(l, i - 1, b) * rec(i + 1, r, b)) % Mod) * C(r - l, i - l)) % Mod;
    461         }
    462     }
    463     return 0;
    464 }
    465 
    466 void solve() {
    467     int n;
    468     cin >> n;
    469     vector<int> b(n);
    470     for (int i = 0; i < n; i++) cin >> b[i];
    471 
    472     int s = accumulate(b.begin(), b.end(), 0ll);
    473     if (s != n * (n + 1) / 2) {
    474         cout << "0\n";
    475         return;
    476     }
    477 
    478     cout << rec(0, n - 1, b) << "\n";
    479 }
    480 
    481 signed main() {
    482     ios_base::sync_with_stdio(0); cin.tie(0);
    483 
    484     fact[0] = 1;
    485     for (int i = 1; i < Max; i++) {
    486         fact[i] = (fact[i - 1] * i) % Mod;
    487     }
    488     for (int i = 0; i < Max; i++) {
    489         ifact[i] = binpow(fact[i], Mod - 2);
    490     }
    491 
    492     int t;
    493     cin >> t;
    494     while (t--) {
    495         solve();
    496     }
    497 }
    498 ```
    499 
    500 **Solution 2 (_Crimson_)**
    501 
    502 Will be added soon.
    503 
    504 **Rate the problem**
    505 
    506 Amazing
    507 
    508 Good
    509 
    510 Ok
    511 
    512 Bad
    513 
    514 Terrible
    515 
    516 [2234F - Vessels, Heights and Two Versions (Hard Version)](/contest/2234/problem/F "Codeforces Round 1102 (Div. 2)")
    517 
    518 Idea: [yanb0](/profile/yanb0 "Candidate Master yanb0")
    519 
    520 **Hint 1**
    521 
    522 Read the solution of C. Try to calculate the answer when the empty vessel is vessel $1$, then somehow change it quickly when moving the empty vessel to be vessel $2$, $3$, etc.
    523 
    524 **Hint 2**
    525 
    526 Consider the highest vessel connection.
    527 
    528 **Hint 3**
    529 
    530 You do not need any advanced data structures. Use a stack.
    531 
    532 **Solution**
    533 
    534 Tutorial is loading...
    535 
    536 **Code (Python)**
    537 
    538 ```
    539 INF = float("inf")
    540  
    541 tt = int(input())
    542 for tc in range(tt):
    543     n = int(input())
    544     h = list(map(int, input().split()))
    545     t = 0
    546     for i in range(n):
    547         if h[i] > h[t]:
    548             t = i
    549     
    550     ls = [0 for i in range(n)]
    551     rs = [0 for i in range(n)]
    552  
    553     sm = [(INF, 0)]
    554     for ti in range(1, n):
    555         i = (ti + t) % n
    556         s = ls[i] + h[i]
    557         c = 1
    558         while sm[-1][0] <= h[i]:
    559             s += sm[-1][1] * (h[i] - sm[-1][0])
    560             c += sm[-1][1]
    561             sm.pop()
    562         sm.append((h[i], c))
    563         ls[(i + 1) % n] = s
    564     
    565     sm = [(INF, 0)]
    566     for ti in range(1, n):
    567         i = (t + n - ti) % n
    568         s = rs[(i + 1) % n] + h[i]
    569         c = 1
    570         while sm[-1][0] <= h[i]:
    571             s += sm[-1][1] * (h[i] - sm[-1][0])
    572             c += sm[-1][1]
    573             sm.pop()
    574         sm.append((h[i], c))
    575         rs[i] = s
    576     
    577     ans = [ls[i] + rs[i] for i in range(n)]
    578     print(*ans)
    579 ```
    580 
    581 **Code (C++)**
    582 
    583 ```
    584 #include <bits/stdc++.h>
    585  
    586 #define int long long
    587  
    588 using namespace std;
    589  
    590 using pii = pair<int, int>;
    591  
    592 void solve() {
    593     int n;
    594     cin >> n;
    595     vector<int> h(n);
    596     for (int i = 0; i < n; i++) cin >> h[i];
    597     int t = max_element(h.begin(), h.end()) - h.begin();
    598     
    599     vector<int> ls(n), rs(n);
    600  
    601     stack<pii> sm;
    602     sm.push({1e18, 0});
    603     for (int ti = 1; ti < n; ti++) {
    604         int i = (ti + t) % n;
    605         int s = ls[i] + h[i], c = 1;
    606         while (sm.top().first <= h[i]) {
    607             s += sm.top().second * (h[i] - sm.top().first);
    608             c += sm.top().second;
    609             sm.pop();
    610         }
    611         sm.push({h[i], c});
    612         ls[(i + 1) % n] = s;
    613     }
    614     
    615     sm = stack<pii>();
    616     sm.push({1e18, 0});
    617     for (int ti = 1; ti < n; ti++) {
    618         int i = (t + n - ti) % n;
    619         int s = rs[(i + 1) % n] + h[i], c = 1;
    620         while (sm.top().first <= h[i]) {
    621             s += sm.top().second * (h[i] - sm.top().first);
    622             c += sm.top().second;
    623             sm.pop();
    624         }
    625         sm.push({h[i], c});
    626         rs[i] = s;
    627     }
    628     
    629     for (int i = 0; i < n; i++) {
    630         cout << ls[i] + rs[i] << " ";
    631     }
    632     cout << "\n";
    633 }
    634  
    635 signed main() {
    636     ios_base::sync_with_stdio(0); cin.tie(0);
    637  
    638     int t;
    639     cin >> t;
    640     while (t--) {
    641         solve();
    642     }
    643 }
    644 ```
    645 
    646 **Rate the problem**
    647 
    648 Amazing
    649 
    650 Good
    651 
    652 Ok
    653 
    654 Bad
    655 
    656 Terrible
    657 
    658 [2234G - Stripe, Token and Two Players](/contest/2234/problem/G "Codeforces Round 1102 (Div. 2)")
    659 
    660 Idea: [yanb0](/profile/yanb0 "Candidate Master yanb0")
    661 
    662 **Hint 1**
    663 
    664 Think of a $\mathcal{O}(n^3)$ solution.
    665 
    666 **Answer to Hint 1**
    667 
    668 DP. For each pair $(cell, strength)$ you can find whether the player that makes the move from the position wins if the game is played optimally.
    669 
    670 **Hint 2**
    671 
    672 There are not many losing positions in this game. Why?
    673 
    674 **Answer to Hint 2**
    675 
    676 The number of losing positions $(i, k)$ for a fixed $k$ with $i \le n$ is no more than $\big\lceil \frac{n}{k + 1} \big\rceil$, since if position $(i, k)$ is a losing position, then all positions $(i + 1, k), (i + 2, k), \ldots, (i + k, k)$ must be winning if they exist. Then the total number of losing positions $(i, k)$ with $i \le n$ is no more than $\mathcal{O}(n \log n)$.
    677 
    678 **Hint 3**
    679 
    680 Try to iterate over cell number $i$ from $n$ to $1$ and explicitly find all losing positions.
    681 
    682 **Hint 4**
    683 
    684 You need to think of a data structure to optimize the solution to $\mathcal{O}(n \log^2 n)$.
    685 
    686 **Solution**
    687 
    688 We'll denote the state of the game where a chip is on cell $i$ and has strength $k$ before using bonuses as $(i, k)$. We need to determine whether position $(1, 1)$ is a winning position.
    689 
    690 Note that the number of losing positions $(i, k)$ for a fixed $k$ with $i \le n$ is no more than $\big\lceil \frac{n}{k + 1} \big\rceil$, since if position $(i, k)$ is a losing position, then all positions $(i + 1, k), (i + 2, k), \ldots, (i + k, k)$ must be winning if they exist. Then the total number of losing positions $(i, k)$ with $i \le n$ is no more than $\mathcal{O}(n \log n)$.
    691 
    692 We will iterate over cell number $i$ from $n$ to $1$ and explicitly find all losing positions.
    693 
    694 Let's maintain a set $S$ containing all $k$ for which there is no losing position $(j, k)$, where $i \lt j \le i + k$. This can be done using a priority queue, adding the event "no more losing positions with strength $k$ on the interval $[i + 1, i + k]$" to position $i - k - 1$ when position $(i, k)$ is losing. (Also, this event addition is done initially for positions $(n + 1, 0), (n + 1, 1), \ldots, (n + 1, n)$, since they are all losing positions, and the strength can be limited to being not more than $n$ without changing the game.) The total number of such events added to the queue will be no more than $\mathcal{O}(n \log n)$ (based on the number of losing positions), which means there will be no more than $\mathcal{O}(n \log n)$ queries to the queue, since in each cell we will only read and delete events related to it. Note that only when we read such an event do we add one element to $S$, and the number of additions to $S$ is also no more than $\mathcal{O}(n \log n)$.
    695 
    696 We will find losing positions for cell $i$ as follows: a position $(i, k)$ is a losing position if and only if, for all $0 \le d \le a_i$, there are no losing positions among positions $(j, k + d)$ for $j \in [i + 1, i + k + d]$, i.e., if and only if $S$ contains all $k, k + 1, \ldots, k + a_i$. To quickly find such $k$, we use the following data structure (we will call it a *block container*):
    697 
    698 There is a set $s$ of natural numbers, initially empty. All numbers in $s$ will be on the interval $[1, n]$, and all operations are guaranteed to be valid (for example, a number already contained in $s$ will not be asked to be added there). A block container can:
    699 
    700 * add a number $x$ to $s$ in $\mathcal{O}(\log n)$;
    701 * find the length of the longest segment of consecutive numbers in $s$ in $\mathcal{O}(1)$;
    702 * find any longest segment of consecutive numbers in $s$ and remove its smallest element from $s$ in $\mathcal{O}(\log n)$.
    703 
    704 **How to implement a block container**
    705 
    706 If written in C++, a container of blocks can be implemented, for example, using two `std::set`s storing the same set of blocks (segments) of consecutive numbers in $s$ (numbers adjacent to the edges of a block must not be in $s$; for example, for $s = {1, 5, 3, 2, 6}$, the set of blocks will be ${[1, 3], [5, 6]}$). The first `std::set` will sort the blocks by their left boundary, and the second by length.
    707 
    708 * When adding a number $x$ to $s$, the container adds a new block $[x, x]$, and then, using the first `std::set`, it finds whether some segments need to be merged with the new one (i.e., whether there are two blocks whose boundaries are adjacent numbers), and, if so, merges them. The container merges segments by removing the old pair of segments from both `std::set`s and adding the merged segment back to each `std::set`.
    709 * To find the longest segment, the container simply accesses the second `std::set`.
    710 * To remove the left element of the segment found above, the container removes the segment from both `std::set`s, increments its left bound by $1$, and, if the segment is still non-empty, adds it back to each `std::set`.
    711 
    712 The code can be written similarly in other languages, if there's a built-in `set` that supports custom sorting and finding the smallest element. Alternatively, a segment tree can be written on a boolean array of length $n$, reflecting the presence/absence ($1$/$0$) of numbers in $s$, storing at a node the boundaries of the longest subsegment of the segment of the node consisting of consecutive 1s.
    713 
    714 Now, let's show how to quickly find the required $k$. We'll store $S$ in a container of blocks. If the length of some block in $S$ is greater than $a_i$ and equals $l + a_i$, the $l$ smallest elements of this block will be losing strengths for cell $i$ — this determines all losing strengths for cell $i$ and only them. Then let's simply remove the smallest element of the longest block while its length is greater than $a_i$ — obviously, and all the removed numbers will be all the losing strengths for cell $i$. The number of requests to the block container for finding and removing when considering cell $i$ is then $1$ more than the number of losing positions $(i, k)$, that is, in total over all cells, no more than $\mathcal{O}(n \log n)$. The number of requests to the block container for adding, as we showed earlier, is also not more than $\mathcal{O}(n \log n)$.
    715 
    716 That is, for each cell, we first process the events coming from the priority queue, load the new elements into the $S$ block container, then find the losing positions, and finally add new events for the next cells to the priority queue. This means we get every losing position in the process; all that remains is to check whether position $(1, 1)$ is a losing position.
    717 
    718 This results in $\mathcal{O}(n \log^2 n)$ for requests to the priority queue, $\mathcal{O}(n \log^2 n)$ for requests to the block container, and a total asymptotic complexity of $\mathcal{O}(n \log^2 n)$.
    719 
    720 **Rate the problem**
    721 
    722 Amazing
    723 
    724 Good
    725 
    726 Ok
    727 
    728 Bad
    729 
    730 Terrible