codeforces-scrape

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

2162.md (25943B)


      1 Source: https://codeforces.com/blog/entry/147242
      2 
      3 [2162A - Красивое среднее](/contest/2162/problem/A "Codeforces Round 1059 (Div. 3)")
      4 
      5 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever")
      6 
      7 **Solution**
      8 
      9 Let's say we have a sequence of numbers with an average equal to $k$.
     10 
     11 Adding a number greater than $k$ increases the average, while adding a smaller one decreases it.
     12 
     13 Therefore, the maximum average subarray is formed by taking the maximum element, since including anything smaller would only lower the average.
     14 
     15 Hence, the final answer is the maximum element of the given array.
     16 
     17 Time Complexity: $O(n)$ per testcase.
     18 
     19 **Implementation**
     20 
     21 ```
     22 #include<bits/stdc++.h>
     23 using namespace std;
     24  
     25 #define ll long long
     26  
     27 int main(){
     28  
     29     int t;
     30     cin >> t;
     31  
     32     while(t--){
     33         int n;
     34         cin >> n;
     35  
     36         vector<int> a(n);
     37         for(int i = 0; i < n; i++) cin >> a[i];
     38  
     39         cout << *max_element(a.begin(), a.end()) << endl;
     40     }
     41  
     42     return 0;
     43 }
     44 ```
     45 
     46 [2162B - Красивая строка](/contest/2162/problem/B "Codeforces Round 1059 (Div. 3)")
     47 
     48 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [tridipta2806](/profile/tridipta2806 "Эксперт tridipta2806")
     49 
     50 **Solution**
     51 
     52 We need to find a non-decreasing subsequence $p$ such that, after removing its characters from the string $s$, the remaining string $x$ becomes a palindrome.
     53 
     54 Observe that if we choose $p$ to consist of all the $0$'s in $s$, then $x$ will contain only $1$'s, which always forms a palindrome. Similarly, if we take $p$ as all the $1$'s, then $x$ will contain only $0$'s, which is also a palindrome.
     55 
     56 In both cases, $p$ is clearly a non-decreasing subsequence (since all its elements are equal).
     57 
     58 Therefore, a valid solution always exists — we can simply output the indices of either all $0$'s or all $1$'s in the string.
     59 
     60 Time Complexity: $O(n)$ per testcase.
     61 
     62 **Implementation**
     63 
     64 ```
     65 #include<bits/stdc++.h>
     66 using namespace std;
     67  
     68 #define ll long long
     69  
     70 int main(){
     71  
     72     int t;
     73     cin >> t;
     74  
     75     while(t--){
     76         int n;
     77         cin >> n;
     78  
     79         string s;
     80         cin >> s;
     81 
     82         vector<int> pos;
     83         for(int i = 0; i < n; i++) if(s[i] == '0') pos.push_back(i + 1);
     84 
     85         cout << (int)pos.size() << '\n';
     86         for(auto& z : pos) cout << z << ' ';
     87 
     88         cout << '\n';
     89     }
     90  
     91     return 0;
     92 }
     93 ```
     94 
     95 [2162C - Красивый XOR](/contest/2162/problem/C "Codeforces Round 1059 (Div. 3)")
     96 
     97 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever")
     98 
     99 **Solution**
    100 
    101 We are allowed to choose any $x$ such that $0 \le x \le a$ and set $a := a \oplus x$. Our goal is to make $a$ equal to $b$.
    102 
    103 Let's think of the binary representation of $a$. Consider the highest set bit (most significant bit) of $a$ and let's assume its position is $\operatorname{msb}(a)$.
    104 
    105 At each operation, we are choosing $x \le a$, which implies that $\operatorname{msb}(x) \le \operatorname{msb}(a)$ (otherwise, we have $x \gt a$).
    106 
    107 $ \displaystyle \begin{matrix} a = (00\dots01\dots\dots)_2 \\ x = (00\dots0\dots1\dots)_2 \end{matrix} $
    108 
    109 Now, we can surely say that $\operatorname{msb}(a \oplus x) \le \operatorname{msb}(a)$.
    110 
    111 Thus, by performing the given operation, $\operatorname{msb}(a)$ will never increase. So, if $\operatorname{msb}(b) \gt \operatorname{msb}(a)$, the answer is $-1$.
    112 
    113 Otherwise, we can always transform $a$ into $b$ in a constructive manner.
    114 
    115 First, we set all bits below $\operatorname{msb}(a)$ one by one to ensure that every required bit can be manipulated. Then, for each bit that is $0$ in $b$, we unset it using an appropriate XOR operation.
    116 
    117 By following this process, we can reach $b$ from $a$ in less than $60$ operations.
    118 
    119 Time Complexity: $O(\log_2(a))$ per testcase.
    120 
    121 **Implementation**
    122 
    123 ```
    124 #include<bits/stdc++.h>
    125 using namespace std;
    126  
    127 int main(){
    128  
    129     int t;
    130     cin >> t;
    131  
    132     while(t--){
    133         int a, b;
    134         cin >> a >> b;
    135         
    136         if(__builtin_clz(a) > __builtin_clz(b)) cout << "-1\n";
    137         else if(a == b) cout << "0\n";
    138         else{
    139             vector<int> val;
    140             for(int i = 0; i < 31; i++){
    141                 int x = (1 << i);
    142                 if(x <= a && (a & x) == 0) a += x, val.push_back(x);
    143             }
    144             for(int i = 0; i < 31; i++){
    145                 int x = (1 << i);
    146                 if(x <= a && (b & x) == 0) val.push_back(x);
    147             }
    148             cout << val.size() << '\n';
    149             for(auto z : val) cout << z << ' ';
    150             cout << '\n';
    151         }
    152     }
    153 }
    154 ```
    155 
    156 [2162D - Красивая перестановка](/contest/2162/problem/D "Codeforces Round 1059 (Div. 3)")
    157 
    158 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever")
    159 
    160 **Solution**
    161 
    162 We denote
    163 
    164 $ \operatorname{query}(1, l, r) = p_l + p_{l + 1} \dots + p_r $ $ \operatorname{query}(2, l, r) = a_l + a_{l + 1} \dots + a_r $
    165 
    166 Now, let us try to find $l$ first.
    167 
    168 Consider two additional arrays representing the prefix sums of the arrays $p$ and $a$, defined as follows:
    169 
    170 $ \mathrm{pref\_sum\_p}[i] = p_1 + p_2 + \dots + p_i, \quad 1 \le i \le n $ $ \mathrm{pref\_sum\_a}[i] = a_1 + a_2 + \dots + a_i, \quad 1 \le i \le n $
    171 
    172 Analysing these, we can say that $\text{pref_sum_a}[i] \ge \text{pref_sum_p}[i]$ for all $i$. In fact, the inequality holds true only when $l \le i \le n$.
    173 
    174 Thus, we can binary search for $l$.
    175 
    176 At each stage, we make $2$ queries $\operatorname{query}(1, 1, \text{mid})$ and $\operatorname{query}(2, 1, \text{mid})$, and by comparing these, we can adjust $\text{left}$ and $\text{right}$ in binary search.
    177 
    178 We can also find $r$ by querying suffixes in a similar way, but that would take a total of $4 \cdot \lceil \log_2(n) \rceil$ queries. This exceeds the query limit.
    179 
    180 Instead, we can query the whole array once and find $r$. In other words,
    181 
    182 $ \operatorname{query}(2, 1, n) - \operatorname{query}(1, 1, n) = r - l + 1 $
    183 
    184 So, after finding $l$, we can find $r$ in $2$ queries. Total queries will be equal to $2 \cdot \lceil \log_2(n) \rceil + 2$ ($ \lt 40$).
    185 
    186 Time Complexity: $O(\log_2(n))$ per testcase.
    187 
    188 **Implementation**
    189 
    190 ```
    191 #include<bits/stdc++.h>
    192 using namespace std;
    193 
    194 #define ll long long
    195 
    196 ll query(int type, int l, int r){
    197     ll x;
    198     cout << type << ' ' << l << ' ' << r << flush << endl;
    199     cin >> x;
    200     return x;
    201 }
    202  
    203 int main(){
    204  
    205     int t;
    206     cin >> t;
    207  
    208     while(t--){
    209         
    210         int n;
    211         cin >> n;
    212 
    213         ll sum = query(2, 1, n);
    214         sum -= ((n * (n + 1)) / 2);
    215 
    216         ll diff = sum - 1;
    217 
    218         int l = 1, r = n;
    219 
    220         while(l < r){
    221             int md = (l + r) / 2;
    222             ll val1 = query(1, 1, md);
    223             ll val2 = query(2, 1, md);
    224 
    225             if(val1 < val2) r = md;
    226             else l = md + 1;
    227         }        
    228 
    229         cout << "!" << ' ' << l << ' ' << diff + l << flush << endl;
    230 
    231     }
    232 }
    233 ```
    234 
    235 [2162E - Красивые палиндромы](/contest/2162/problem/E "Codeforces Round 1059 (Div. 3)")
    236 
    237 Idea: [wuhudsm](/profile/wuhudsm "Мастер wuhudsm") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever")
    238 
    239 **Solution**
    240 
    241 Instead of carefully choosing all $k$ elements individually, it is sufficient to pick **three distinct integers** $x$, $y$, and $z$ and repeat them cyclically — that is, append
    242 
    243 $x, y, z, x, y, z, \dots$
    244 
    245 until we perform $k$ operations. For $n \ge 3$, we can always find such $x$, $y$, $z$ that add no extra palindromic subarrays.
    246 
    247 Now let's try to find such integers $x$, $y$, $z$. There will be two cases.
    248 
    249 **Case 1**: $a$ is a permutation of ${1,2,3, \dots ,n}$.
    250 
    251 If the array $a$ is a permutation, we can simply choose the first three elements of $a$ for the construction. That is, let $x = a_1$, $y = a_2$, and $z = a_3$. Since all elements in a permutation are distinct, these choices guarantee that $x$, $y$, and $z$ are distinct and add no extra palindromic subarrays.
    252 
    253 **Case 2**: $a$ is not a permutation of ${1,2,3, \dots ,n}$.
    254 
    255 If the array $a$ is not a permutation, we can choose $x$ to be any integer that does not appear in $a$. Let $z$ be the last element of the array, and choose $y$ as any integer different from both $x$ and $z$. These three numbers will always be distinct and add no extra palindromic subarrays.
    256 
    257 Time Complexity: $O(n + k)$ per testcase.
    258 
    259 **Implementation**
    260 
    261 ```
    262 #include<bits/stdc++.h>
    263 using namespace std;
    264  
    265 int main(){
    266  
    267     int t;
    268     cin >> t;
    269  
    270     while(t--){
    271         
    272         int n, k;
    273         cin >> n >> k;
    274 
    275         vector<int> a(n), cnt(n + 1, 0);
    276         for(int i = 0; i < n; i++) cin >> a[i], cnt[a[i]]++;
    277 
    278         int x = -1;
    279         for(int i = 1; i <= n; i++) if(cnt[i] == 0){
    280             x = i;
    281             break;
    282         }
    283 
    284         if(x == -1){
    285             for(int i = 0; i < k; i++) cout << a[n - 3 + (i % 3)] << ' ';
    286             cout << '\n';
    287         }
    288         else{
    289             int y = -1;
    290             for(int i = 1; i <= n; i++) if(i != x && i != a[n - 1]){
    291                 y = i;
    292                 break;
    293             }
    294             vector<int> v = {x, y, a[n - 1]};
    295             for(int i = 0; i < k; i++) cout << v[i % 3] << ' ';
    296             cout << '\n';
    297         }
    298 
    299     }
    300 }
    301 ```
    302 
    303 [2162F - Красивые отрезки](/contest/2162/problem/F "Codeforces Round 1059 (Div. 3)")
    304 
    305 Idea: [frostcat](/profile/frostcat "Новичок frostcat"), [wuhudsm](/profile/wuhudsm "Мастер wuhudsm"), [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever")
    306 
    307 **Solution**
    308 
    309 Note that if $[0,2,1]$ is a subsequence of permutation $p$, any interval that includes $0$ and $1$ must also include $2$. This implies that $\operatorname{mex}$ of any interval will not be equal to $2$. So, $2 \notin M$. Hence, $\operatorname{mex}(M) \le 2$.
    310 
    311 Thus, we can always ensure that $\operatorname{mex}(M) \le 2$. Now, we only need to check when $\operatorname{mex}(M) = 0$ and $\operatorname{mex}(M) = 1$ are possible.
    312 
    313 For $\operatorname{mex}(M)$ to be equal to $0$, $\operatorname{mex}$ of every interval must be positive. So, every interval must include $0$. This is possible only when all intervals intersect at a common point — that is, there exists at least one point that lies within every interval. Then we place $0$ at some common point and fill the remaining permutation.
    314 
    315 Otherwise, for $\operatorname{mex}(M)$ to be equal to $1$, $\operatorname{mex}$ of each interval must not be equal to $1$. To ensure this, we have to place $0$ and $1$ in such a way that if an interval includes $0$, it must also include $1$. This is possible if there exists a point that is not simultaneously the starting point of one interval and the ending point of another. In other words, we should be able to find a position that does not act as both a left and a right boundary. Then we place $0$ at such a point and $1$ adjacent to it.
    316 
    317 Else, we place $[0,2,1]$ as a subsequence first and then build the remaining permutation.
    318 
    319 Time Complexity: $O(n + m)$ per testcase.
    320 
    321 **Implementation**
    322 
    323 ```
    324 #include <bits/stdc++.h>
    325 using namespace std;
    326 #define int long long
    327 #define INF (int)1e18
    328 
    329 void Solve() 
    330 {
    331     
    332     int n, m; cin >> n >> m;
    333     
    334     vector <int> l(m), r(m), f(n + 1), st(n + 1, 0), en(n + 1);
    335     for (int i = 0; i < m; i++){
    336         cin >> l[i] >> r[i];
    337         st[l[i]] = 1;
    338         en[r[i]] = 1;
    339         for (int j = l[i]; j <= r[i]; j++){
    340             f[j]++;
    341         }
    342     }
    343     
    344     vector <int> ans(n + 1, -1);
    345     
    346     auto fill = [&](){
    347         vector <bool> used(n, false);
    348         for (int i = 1; i <= n; i++) if (ans[i] != -1) used[ans[i]] = true;
    349         
    350         int p = 0;
    351         for (int i = 1; i <= n; i++){
    352             if (ans[i] == -1){
    353                 while (used[p]) p++;
    354                 
    355                 ans[i] = p;
    356                 used[p] = true;
    357             }
    358         }
    359         
    360         for (int i = 1; i <= n; i++){
    361             cout << ans[i] << " \n"[i == n];
    362         }
    363     };
    364     
    365     for (int i = 1; i <= n; i++){
    366         if (f[i] == m){
    367             int ptr = 1;
    368             ans[i] = 0;
    369             
    370             fill();
    371             return;
    372         }
    373     }
    374     
    375     for (int i = 1; i < n; i++){
    376         if (en[i] == 0){
    377             ans[i] = 0;
    378             ans[i + 1] = 1;
    379             fill();
    380             return;
    381         }
    382         
    383         if (st[i + 1] == 0){
    384             ans[i] = 1;
    385             ans[i + 1] = 0;
    386             fill();
    387             return;
    388         }
    389     }
    390     
    391     assert(n >= 3);
    392     ans[1] = 0;
    393     ans[2] = 2;
    394     ans[3] = 1;
    395     
    396     fill();
    397 }
    398 
    399 int32_t main() 
    400 {
    401     ios_base::sync_with_stdio(0);
    402     cin.tie(0);
    403     int t = 1;
    404     cin >> t;
    405     for(int i = 1; i <= t; i++) 
    406     {
    407         Solve();
    408     }
    409     
    410     return 0;
    411 }
    412 ```
    413 
    414 [2162G - Красивое дерево](/contest/2162/problem/G "Codeforces Round 1059 (Div. 3)")
    415 
    416 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever")
    417 
    418 **Solution**
    419 
    420 We have to construct a tree with $n$ vertices such that $S = \sum_{{u, v} \in E} (u \cdot v)$ is a perfect square.
    421 
    422 Instead of making it any random perfect square, let's try to make $S = (f(n))^2$ where $f(n)$ is an integer function of $n$.
    423 
    424 Now, let's check if we can make $f(n) = n$. For $n = 5$, we can consider the following tree
    425 
    426 $5-1-2-3-4$
    427 
    428 where $S = 25 = (5)^2$.
    429 
    430 Now that we know we have a tree $T$ with $n$ ($=5$) vertices having $S = n^2$. Using this, let's try to make a tree $T'$ with $n + 1$ vertices such that $S' = (n + 1)^2$. Note that $S' - S = 2n + 1$. So, while constructing $T'$, we have to add a new vertex $(n + 1)$ and also adjust this extra sum $2n + 1$.
    431 
    432 We can achieve this in the following manner:
    433 
    434 * add an edge between $1$ and $n + 1$,
    435 * remove the edge between $1$ and $n$,
    436 * add an edge between $2$ and $n$.
    437 
    438 This analogy can be extended for all $n \ge 5$. Such trees have the following structure:
    439 
    440 ![](/predownloaded/8a/88/8a88f790f81cf65182f36cf963f910ef0c9a3c54.png)
    441 
    442 So, we can always make $S = n^2$ for all $n \ge 5$. For $n \lt 5$, we can just print sample outputs.
    443 
    444 One can also assume $f(n) = n + 1$ and construct a similar solution with $S = (n + 1)^2$.
    445 
    446 Time Complexity: $O(n)$ per testcase.
    447 
    448 **Implementation**
    449 
    450 ```
    451 #include<bits/stdc++.h>
    452 using namespace std;
    453  
    454 int main(){
    455  
    456     int t;
    457     cin >> t;
    458  
    459     while(t--){
    460  
    461         int n;
    462         cin >> n;
    463         
    464         if(n == 2){
    465             cout << -1 << '\n';
    466             continue;
    467         }
    468  
    469         if(n == 3){
    470             cout << "1 3\n2 3\n";
    471             continue;
    472         }
    473  
    474         if(n == 4){
    475             cout << "1 2\n3 1\n4 1\n";
    476             continue;
    477         }
    478  
    479         cout << "1 2\n";
    480         cout << "2 3\n";
    481         cout << "3 4\n";
    482  
    483         cout << "1 " << n << '\n';
    484  
    485         for(int i = 5; i < n; i++) cout << 2 << ' ' << i << '\n';
    486     }
    487 }
    488 ```
    489 
    490 [2162H - Красивая задача](/contest/2162/problem/H "Codeforces Round 1059 (Div. 3)")
    491 
    492 Idea: [wuhudsm](/profile/wuhudsm "Мастер wuhudsm") Preparation: [wuhudsm](/profile/wuhudsm "Мастер wuhudsm")
    493 
    494 **Spoiler**
    495 
    496 ![ 2025-10-18 065201.png](/predownloaded/3d/8f/3d8fb9c96462a71b0f9ea8494f91886d578c1d9f.png)
    497 
    498 **Solution**
    499 
    500 When the value of $f$ is 1 for $[l_i, r_i]$, all numbers in $[l_i, r_i]$ are either $\leq x$ or $\geq x$.
    501 
    502 We observe that for each interval, we need to divide the intervals into S-intervals (smaller) and B-intervals (bigger). S-intervals can only contain numbers $\leq x$, and B-intervals can only contain numbers $\geq x$.
    503 
    504 Assuming we have fixed the S-intervals and B-intervals. For each index $i$, there are 4 types:
    505 
    506 * Type 1: $i$ is covered only by S-intervals;
    507 * Type 2: $i$ is covered only by B-intervals;
    508 * Type 3: $i$ is covered by both S-intervals and B-intervals;
    509 * Type 4: $i$ is covered by neither S-intervals nor B-intervals.
    510 
    511 Let $cnt_s$ be the number of values $ \lt x$, and $cnt_b$ be the number of values $ \gt x$.
    512 
    513 When there are no type 4 indices, we only need to check whether:
    514 
    515 * $cnt_s \leq$ (total number of type 1 indices)
    516 * $cnt_b \leq$ (total number of type 2 indices)
    517 
    518 When type 4 indices exist, we only need to make a slight modification to the condition (this modification is left to the reader).
    519 
    520 Consider a simpler case: all intervals are non-overlapping. In this case, the problem reduces to a classic knapsack problem, where each interval becomes an independent item. We consider extending the idea of DP to the original problem.
    521 
    522 We find that intervals that are contained within others are useless and can be removed. Then, the intervals can be sorted by their left endpoints. This way, for $i \lt j$, we can ensure $l_i \lt l_j$ and $r_i \lt r_j$. Then, we perform DP based on the order of the intervals.
    523 
    524 We define:
    525 
    526 $dp[i][j][k = 0 \text{ or } 1]$: For the first $i$ intervals, the total number of type 1 indices is $j$, and the last interval is an S-interval ($k = 0$) or a B-interval ($k = 1$), the maximum total number of type 2 indices obtained.
    527 
    528 Let $inslen[i]$ be the length of the intersection between the $i$-th interval and the $(i-1)$-th interval.
    529 
    530 Transitions:
    531 
    532 * $dp[i][j][0] = \max(dp[i-1][j - inslen[i]][0], dp[i-1][j - inslen[i]][1] - inslen[i])$
    533 * $dp[i][j][1] = \max(dp[i-1][j][1] + inslen[i], dp[i-1][j + inslen[i]][1] + inslen[i])$
    534 
    535 Note: For intervals $(i-2)$, $(i-1)$, $i$, if the type of interval $(i-1)$ is different from both $(i-2)$ and $i$, and $r[i-2] \geq l[i]$, some overlapping parts may be subtracted repeatedly. However, we find that this does not affect the final answer because it is not better than the answer when all three intervals are of the same type. Here, a common DP idea is applied: if "incorrect" states are recorded but they cannot be optimal, the DP transitions can remain unchanged (a similar idea is used in: <https://codeforces.com/contest/1859/problem/E)>.
    536 
    537 | State 1 | State 2 |
    538 | --- | --- |
    539 | 2025-10-18 064710.png) | 2025-10-18 064836.png |
    540 | Some overlapping parts (in the middle) are subtracted repeatedly. | Better because the value range of the middle positions is strictly larger. |
    541 
    542 Afterward, answering queries using the DP array is trivial. The time complexity is $O(n^2)$.
    543 
    544 ---
    545 
    546 There is another DP approach. Let $b[i]$ be the smallest $j \leq i$ such that $j$ and $i$ are covered by the same interval. Then, if position $i$ is filled with a number $ \lt x$, we can deduce that all numbers in $a'[b[i], \ldots, i]$ must be $ \lt x$, and so on. This way, we can write a DP that transitions position by position, without pre-processing each interval.
    547 
    548 For details, refer to [Dominater069](/profile/Dominater069 "Легендарный гроссмейстер Dominater069") 's code.
    549 
    550 **Implementation1(wuhudsm)**
    551 
    552 ```
    553 #include <map>
    554 #include <set>
    555 #include <cmath>
    556 #include <ctime>
    557 #include <queue>
    558 #include <stack>
    559 #include <cstdio>
    560 #include <cstdlib>
    561 #include <vector>
    562 #include <cstring>
    563 #include <algorithm>
    564 #include <iostream>
    565 #include <bitset>
    566 #include <unordered_map>
    567 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    568 using namespace std;
    569 typedef double db;
    570 typedef long long ll;
    571 typedef unsigned long long ull;
    572 const int N=3010;
    573 const int LOGN=28;
    574 const ll  TMD=0;
    575 const ll  INF=100000000;
    576 int T,n,m;
    577 int a[N],cnt[N],mxr[N];
    578 int dp[N][N][2];
    579 
    580 /*
    581  * stuff you should look for
    582  * [Before Submission]
    583  * array bounds, initialization, int overflow, special cases (like n=1), typo
    584  * [Still WA]
    585  * check typo carefully
    586  * casework mistake
    587  * special bug
    588  * stress test
    589  */
    590 
    591 //--------------------------------------------------------------------------
    592 
    593 struct seg
    594 {
    595 	int l,r;
    596 
    597 	seg() {}
    598 
    599 	seg(int l,int r):l(l),r(r){}
    600 
    601 	int len()
    602 	{
    603 	    return r-l+1;
    604 	}
    605 };
    606 
    607 seg getins(seg x,seg y)
    608 {
    609 	if(x.l>y.l) swap(x,y);
    610 	if(x.r<y.l) return seg(INF,INF);
    611 	if(x.r<y.r) return seg(y.l,x.r);
    612 	else return seg(y.l,y.r);
    613 }
    614 
    615 //--------------------------------------------------------------------------
    616 
    617 void init()
    618 {
    619     cin>>n>>m;
    620     for(int i=0;i<=n;i++)
    621         mxr[i]=0;
    622     for(int i=1;i<=n;i++)
    623         cin>>a[i];
    624     for(int i=1;i<=m;i++)
    625     {
    626         int l,r;
    627         cin>>l>>r;
    628         mxr[l]=max(mxr[l],r);
    629     }
    630     for(int i=0;i<=n+4;i++)
    631         for(int j=0;j<=n+4;j++)
    632             dp[i][j][0]=dp[i][j][1]=-INF;
    633 }
    634 
    635 void solve()
    636 {
    637     int sz,cfree=0;
    638     vector<int> tag(n+4);
    639     vector<seg> vs;
    640     for(int i=1;i<=n;i++)
    641     {
    642         if(!mxr[i]) continue;
    643         if(vs.empty()||vs.back().r<mxr[i])
    644             vs.push_back(seg(i,mxr[i]));
    645     }
    646     sz=vs.size();
    647     dp[1][0][0]=vs[0].len();
    648     dp[1][vs[0].len()][1]=0;
    649     for(int i=2;i<=sz;i++)
    650     {
    651         seg cur=vs[i-1],ins=getins(vs[i-2],vs[i-1]);
    652         int len_ins=(ins.l==INF?0:ins.len());
    653         for(int j=0;j<=n;j++)
    654         {
    655             dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][0]+cur.len()-len_ins);
    656             if(j+len_ins<=n)
    657                 dp[i][j][0]=max(dp[i][j][0],dp[i-1][j+len_ins][1]+cur.len()-len_ins);
    658             if(j-(cur.len()-len_ins)>=0)
    659             {
    660                 dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-(cur.len()-len_ins)][1]);
    661                 dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-(cur.len()-len_ins)][0]-len_ins);
    662             }
    663         }
    664     }
    665     for(int i=0;i<vs.size();i++)
    666         for(int j=vs[i].l;j<=vs[i].r;j++)
    667             tag[j]=1;
    668     for(int i=1;i<=n;i++)
    669         if(!tag[i]) cfree++;
    670     for(int i=1;i<=n;i++)
    671     {
    672         int s=0,b=0;
    673         for(int j=1;j<=n;j++)
    674         {
    675             if(a[j]<i) s++;
    676             else if(a[j]>i) b++;
    677         }
    678         int flg=0;
    679         for(int j=0;j<=n;j++)
    680         {
    681             int need1=max(0,s-j),need2=max(0,b-max(dp[sz][j][0],dp[sz][j][1]));
    682             flg|=(cfree>=need1+need2);
    683         }
    684         cout<<flg;
    685     }
    686     cout<<"\n";
    687 }
    688 
    689 //-------------------------------------------------------
    690 
    691 void gen_data()
    692 {
    693     srand(time(NULL));
    694 }
    695 
    696 int bruteforce()
    697 {
    698     return 0;
    699 }
    700 
    701 //-------------------------------------------------------
    702 
    703 int main()
    704 {
    705     fastio;
    706 
    707     cin>>T;
    708 	while(T--)
    709 	{
    710 		init();
    711 		solve();
    712 
    713 		/*
    714 
    715 		//Stress Test
    716 
    717 		gen_data();
    718 		auto ans1=solve(),ans2=bruteforce();
    719 		if(ans1==ans2) printf("OK!\n");
    720 		else
    721 		{
    722 			//Output Data
    723  		}
    724 
    725 		*/
    726 	}
    727 
    728 	return 0;
    729 }
    730 ```
    731 
    732 **Implementation2 (Dominater069)**
    733 
    734 ```
    735 #include <bits/stdc++.h>
    736 using namespace std;
    737 #define INF (int)1e9
    738 
    739 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
    740 
    741 void Solve() 
    742 {
    743     // x <= min or x >= max 
    744     // min < x < max is bad 
    745     // => in range if both smaller and larger exists, cooked 
    746     // just spam smaller at one end, and larger at other end? 
    747     // i <-> j if there exists interval covering both 
    748     // if i <-> j, cannot have diff type on i and j 
    749     // dp[i][number of 0s] = max number of 1s, but also need to know what is the last 0 / 1 position 
    750     // we can extend last character always 
    751     // we can extend other character only after some gap 
    752     // prefmax?
    753     
    754     int n, m; cin >> n >> m;
    755     
    756     vector <int> a(n + 1), f(n + 1);
    757     for (int i = 1; i <= n; i++){
    758         cin >> a[i];
    759         f[a[i]]++;
    760     }
    761     
    762     vector <int> b(n + 1), c(n + 1);
    763     for (int i = 1; i <= n; i++){
    764         b[i] = c[i] = i;
    765     }
    766     for (int i = 1; i <= m; i++){
    767         int l, r; cin >> l >> r;
    768         for (int j = l; j <= r; j++){
    769             b[j] = min(b[j], l);
    770             c[j] = max(c[j], r);
    771         }
    772     }
    773     
    774     // vector dp(n + 1, vector(n + 1, vector <int>(2, -INF)));
    775     // vector pref(n + 1, vector(n + 1, vector <int>(2, -INF)));
    776     int dp[n + 1][n + 1][2];
    777     int pref[n + 1][n + 1][2];
    778     
    779     for (int i = 0; i <= n; i++){
    780         for (int j = 0; j <= n; j++){
    781             for (int k = 0; k < 2; k++){
    782                 dp[i][j][k] = -INF;
    783                 pref[i][j][k] = -INF;
    784             }
    785         }
    786     }
    787     
    788     dp[0][0][0] = dp[0][0][1] = 0;
    789     pref[0][0][0] = pref[0][0][1] = 0;
    790     
    791     for (int i = 1; i <= n; i++){
    792         for (int x = 0; x <= n; x++){
    793             for (int y = 0; y < 2; y++){
    794                 for (int z = 0; z < 2; z++){
    795                     if (y == z){
    796                         int px = x - (y == 0);
    797                         if (px >= 0){
    798                             dp[i][x][y] = max(dp[i][x][y], pref[i - 1][px][z] + (y == 1));
    799                         }
    800                     } else {
    801                         int px = x - (y == 0);
    802                         int lim = b[i] - 1;
    803                         if (px >= 0){
    804                             dp[i][x][y] = max(dp[i][x][y], pref[lim][px][z] + (y == 1));
    805                         }
    806                     }
    807                 }
    808                 
    809                 pref[i][x][y] = max(pref[i - 1][x][y], dp[i][x][y]);
    810             }
    811         }
    812     }
    813     
    814     for (int i = 1; i <= n; i++){
    815         int lower = 0;
    816         int upper = 0;
    817         for (int j = 1; j < i; j++) lower += f[j];
    818         for (int j = i + 1; j <= n; j++) upper += f[j];
    819         
    820         if (pref[n][lower][0] >= upper || pref[n][lower][1] >= upper){
    821             cout << "1";
    822         } else {
    823             cout << "0";
    824         }
    825     }
    826     cout << "\n";
    827 }
    828 
    829 int32_t main() 
    830 {
    831     auto begin = std::chrono::high_resolution_clock::now();
    832     ios_base::sync_with_stdio(0);
    833     cin.tie(0);
    834     int t = 1;
    835     // freopen("in",  "r", stdin);
    836     // freopen("out", "w", stdout);
    837     
    838     cin >> t;
    839     for(int i = 1; i <= t; i++) 
    840     {
    841         //cout << "Case #" << i << ": ";
    842         Solve();
    843     }
    844     auto end = std::chrono::high_resolution_clock::now();
    845     auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    846     cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    847     return 0;
    848 }
    849 ```