codeforces-scrape

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

2143.md (15038B)


      1 Source: https://codeforces.com/blog/entry/146526
      2 
      3 Thanks everybody for participating in the round!
      4 
      5 [2143A - Вычитание всех длин](/contest/2143/problem/A "Codeforces Round 1051 (Div. 2)")
      6 
      7 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Editorial: [MateiKing80](/profile/MateiKing80 "Мастер MateiKing80")
      8 
      9 **Solution**
     10 
     11 Tutorial is loading...
     12 
     13 **Code**
     14 
     15 ```
     16 #include <iostream>
     17 #include <cassert>
     18 #include <vector>
     19 #include <algorithm>
     20  
     21 #define debug(x) #x << " = " << x << '\n'
     22  
     23 using ll = long long;
     24 #define YES std::cout << "YES" << std::endl;
     25 #define NO std::cout << "NO" << std::endl;
     26  
     27 void solve() {
     28   int n;
     29   std::cin >> n;
     30   std::vector<int> p(n);
     31   for (int i = 0; i < n; i++) {
     32     std::cin >> p[i];
     33   }  
     34  
     35   int l = 0, r = n - 1;
     36   for (int i = 1; i <= n; i++) {
     37     if (p[l] == i) {
     38       l++;
     39     } else if (p[r] == i) {
     40       r--;
     41     } else {
     42       NO;
     43       return;
     44     }
     45   }
     46   YES;
     47 }
     48  
     49 int main() {
     50    int t;
     51    std::cin >> t;
     52    for (int tc = 1; tc <= t; tc++) {
     53     solve();
     54    }
     55  
     56   return 0;
     57 }
     58 ```
     59 
     60 [2143B - Скидки](/contest/2143/problem/B "Codeforces Round 1051 (Div. 2)")
     61 
     62 Author: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio"), Preparation: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio"), Editorial: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio")
     63 
     64 **Solution**
     65 
     66 Tutorial is loading...
     67 
     68 **Code**
     69 
     70 ```
     71 #include <bits/stdc++.h>
     72  
     73 using namespace std;
     74  
     75 int n, k, a[200005], b[200005];
     76  
     77 void testcase()
     78 {
     79     cin >> n >> k;
     80     for (int i = 1; i <= n; i++)
     81         cin >> a[i];
     82     for (int i = 1; i <= k; i++)
     83         cin >> b[i];
     84     long long ans = 0;
     85     sort(a + 1, a + n + 1);
     86     sort(b + 1, b + k + 1);
     87     for (int i = 1; i <= n; i++)
     88         ans += a[i];
     89     long long id = n + 1;
     90     for (int i = 1; i <= k; i++)
     91     {
     92         id -= b[i];
     93         if (id >= 1)
     94             ans -= a[id];
     95     }
     96     cout << ans << '\n';
     97 }
     98  
     99 int main()
    100 {
    101     int tc;
    102     cin >> tc;
    103     while (tc--)
    104         testcase();
    105     return 0;
    106 }
    107 ```
    108 
    109 [2143C - Максимальное дерево](/contest/2143/problem/C "Codeforces Round 1051 (Div. 2)")
    110 
    111 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Editorial: [tvladm](/profile/tvladm "Кандидат в мастера tvladm")
    112 
    113 **Solution**
    114 
    115 Tutorial is loading...
    116 
    117 **Code**
    118 
    119 ```
    120 #include <iostream>
    121 #include <cassert>
    122 #include <vector>
    123 #include <algorithm>
    124 #include <queue>
    125  
    126 #define debug(x) #x << " = " << x << '\n'
    127  
    128 using ll = long long;
    129 #define YES std::cout << "YES\n"
    130 #define NO std::cout << "NO\n"
    131  
    132 struct Edge {
    133   int u, v, x, y;
    134 };
    135  
    136 void solve() {
    137   int n;
    138   std::cin >> n;
    139  
    140   std::vector<int> deg(n, 0);
    141   std::vector<std::vector<int>> g(n);
    142   std::vector<std::vector<int>> gg(n);
    143  
    144   std::vector<Edge> e(n - 1);
    145  
    146   for (auto &[u, v, x, y] : e) {
    147     std::cin >> u >> v >> x >> y;
    148     u--, v--;
    149     if (x > y) {
    150       g[u].push_back(v);
    151       gg[v].push_back(u);
    152       deg[u]++;
    153     } else {
    154       g[v].push_back(u);
    155       gg[u].push_back(v);
    156       deg[v]++;
    157     }
    158   }
    159  
    160   std::queue<int> q;
    161   for (int i = 0; i < n; i++) {
    162     if (deg[i] == 0) {
    163       q.push(i);
    164     }
    165   }
    166  
    167   std::vector<int> p(n);
    168  
    169   for (int i = 1; i <= n; i++) {
    170     int u = q.front();
    171     p[u] = i;
    172     q.pop();
    173  
    174     for (const auto &v : gg[u]) {
    175       deg[v]--;
    176       if (deg[v] == 0) {
    177         q.push(v);
    178       }
    179     }
    180   }
    181   
    182   for (auto [u, v, x, y] : e) {
    183     if (x > y) {
    184       assert(p[u] > p[v]);
    185     } else if (x < y) {
    186       assert(p[u] < p[v]);
    187     }
    188   }
    189  
    190   for (int x : p) {
    191     std::cout << x << ' ';
    192   }
    193 }
    194  
    195 int main() {
    196   #ifdef LOCAL
    197 freopen("input.txt", "r", stdin);
    198   #endif
    199   std::ios_base::sync_with_stdio(false);
    200   std::cin.tie(0);
    201   std::cout.tie(0);
    202  
    203    int t;
    204    std::cin >> t;
    205    for (int tc = 1; tc <= t; tc++) {
    206     std::cerr << "Case #" << tc << ":\n";
    207     solve();
    208     std::cout << '\n';
    209    }
    210  
    211   return 0;
    212 }
    213 ```
    214 
    215 [2143D1 - Раскраска графа инверсий (простая версия)](/contest/2143/problem/D1 "Codeforces Round 1051 (Div. 2)")
    216 
    217 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio"), Editorial: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio")
    218 
    219 **Solution**
    220 
    221 Tutorial is loading...
    222 
    223 **Code**
    224 
    225 ```
    226 #include <bits/stdc++.h>
    227  
    228 using namespace std;
    229  
    230 const int NMAX = 3000;
    231 const int modulo = 1e9 + 7;
    232  
    233 void addSelf(int &x, int y)
    234 {
    235     x += y;
    236     if (x >= modulo)
    237         x -= modulo;
    238 }
    239  
    240 int add(int x, int y)
    241 {
    242     addSelf(x, y);
    243     return x;
    244 }
    245  
    246 int n, a[NMAX + 5], b[NMAX + 5];///b -> initial array, a -> equivalent permutation
    247 int dp[2][NMAX + 1][NMAX + 1];///considering elements 1..i, the biggest value is j, and the biggest value preceeded by a bigger one is q
    248  
    249 void testcase()
    250 {
    251     cin >> n;
    252     for (int i = 1; i <= n; i++)
    253         cin >> b[i];
    254     for (int i = 1; i <= n; i++)
    255     {
    256         a[i] = 1;
    257         for (int j = 1; j < i; j++)
    258             if (b[j] <= b[i])
    259                 a[i]++;
    260         for (int j = i + 1; j <= n; j++)
    261             if (b[j] < b[i])
    262                 a[i]++;
    263     }
    264     for (int i = 0; i < 2; i++)
    265         for (int j = 0; j <= n; j++)
    266             for (int q = 0; q <= n; q++)
    267                 dp[i][j][q] = 0;
    268     dp[0][0][0] = 1;
    269     int cr = 0;
    270     for (int i = 1; i <= n; i++)
    271     {
    272         cr ^= 1;
    273         int x = a[i];
    274         for (int j = 0; j <= n; j++)
    275             for (int q = 0; q <= n; q++)
    276                 dp[cr][j][q] = dp[cr ^ 1][j][q];
    277         for (int j = 0; j <= n; j++)
    278         {
    279             for (int q = 0; q <= j; q++)
    280             {
    281                 if (dp[cr ^ 1][j][q] == 0)
    282                     continue;
    283                 if (j > x and x > q)
    284                     addSelf(dp[cr][j][x], dp[cr ^ 1][j][q]);
    285                 else if (x > j)
    286                     addSelf(dp[cr][x][q], dp[cr ^ 1][j][q]);
    287             }
    288         }
    289     }
    290     int ans = 0;
    291     for (int j = 0; j <= n; j++)
    292     {
    293         for (int q = 0; q <= n; q++)
    294             addSelf(ans, dp[cr][j][q]);
    295     }
    296     cout << ans << '\n';///empty subsequence inclusive
    297 }
    298  
    299 int main()
    300 {
    301     int tc;
    302     cin >> tc;
    303     while (tc--)
    304         testcase();
    305     return 0;
    306 }
    307 ```
    308 
    309 [2143D2 - Раскраска графа инверсий (сложная версия)](/contest/2143/problem/D2 "Codeforces Round 1051 (Div. 2)")
    310 
    311 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio"), Editorial: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio")
    312 
    313 **Solution**
    314 
    315 Tutorial is loading...
    316 
    317 **Code**
    318 
    319 ```
    320 #include <bits/stdc++.h>
    321  
    322 using namespace std;
    323  
    324 const int NMAX = 3000;
    325 const int modulo = 1e9 + 7;
    326  
    327 void addSelf(int &x, int y)
    328 {
    329     x += y;
    330     if (x >= modulo)
    331         x -= modulo;
    332 }
    333  
    334 int add(int x, int y)
    335 {
    336     addSelf(x, y);
    337     return x;
    338 }
    339  
    340 int n, a[NMAX + 5], b[NMAX + 5];///b -> initial array, a -> equivalent permutation
    341 int bit_lin[NMAX + 5][NMAX + 5], bit_col[NMAX + 5][NMAX + 5];///will use an offset of one because of [0..n] range
    342  
    343 void update_lin(int lin, int pos, int val)
    344 {
    345     pos++;
    346     for (int i = pos; i <= n + 1; i += (i & -i))
    347         addSelf(bit_lin[lin][i], val);
    348 }
    349  
    350 void update_col(int col, int pos, int val)
    351 {
    352     pos++;
    353     for (int i = pos; i <= n + 1; i += (i & -i))
    354         addSelf(bit_col[col][i], val);
    355 }
    356  
    357 int query_lin(int lin, int pos)
    358 {
    359     pos++;
    360     int rr = 0;
    361     for (int i = pos; i > 0; i -= (i & -i))
    362         addSelf(rr, bit_lin[lin][i]);
    363     return rr;
    364 }
    365  
    366 int query_col(int col, int pos)
    367 {
    368     pos++;
    369     int rr = 0;
    370     for (int i = pos; i > 0; i -= (i & -i))
    371         addSelf(rr, bit_col[col][i]);
    372     return rr;
    373 }
    374  
    375 void testcase()
    376 {
    377     cin >> n;
    378     for (int i = 1; i <= n; i++)
    379         cin >> b[i];
    380     for (int i = 1; i <= n; i++)
    381     {
    382         a[i] = 1;
    383         for (int j = 1; j < i; j++)
    384             if (b[j] <= b[i])
    385                 a[i]++;
    386         for (int j = i + 1; j <= n; j++)
    387             if (b[j] < b[i])
    388                 a[i]++;
    389     }
    390     for (int i = 0; i <= n + 1; i++)
    391         for (int j = 0; j <= n + 1; j++)
    392             bit_lin[i][j] = bit_col[i][j] = 0;
    393     update_lin(0, 0, 1);
    394     update_col(0, 0, 1);
    395     for (int i = 1; i <= n; i++)
    396     {
    397         vector<pair<int, pair<int, int>>> buffs;///where to update at the end
    398         int x = a[i];
    399         for (int j = x + 1; j <= n; j++)
    400         {
    401             int lin, col, buff;
    402             lin = j;
    403             col = x;
    404             buff = query_lin(j, x - 1);
    405             buffs.push_back({buff, {lin, col}});
    406         }
    407         for (int q = 0; q < x; q++)
    408         {
    409             int lin, col, buff;
    410             lin = x;
    411             col = q;
    412             buff = query_col(q, x - 1);
    413             buffs.push_back({buff, {lin, col}});
    414         }
    415         for (auto it : buffs)
    416         {
    417             update_lin(it.second.first, it.second.second, it.first);
    418             update_col(it.second.second, it.second.first, it.first);
    419         }
    420     }
    421     int ans = 0;
    422     for (int lin = 0; lin <= n; lin++)
    423         addSelf(ans, query_lin(lin, n));
    424     cout << ans << '\n';
    425 }
    426  
    427 int main()
    428 {
    429     int tc;
    430     cin >> tc;
    431     while (tc--)
    432         testcase();
    433     return 0;
    434 }
    435 ```
    436 
    437 [2143E - Сделать хорошей](/contest/2143/problem/E "Codeforces Round 1051 (Div. 2)")
    438 
    439 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Editorial: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM")
    440 
    441 **Solution**
    442 
    443 Tutorial is loading...
    444 
    445 **Code**
    446 
    447 ```
    448 #include <iostream>
    449 #include <cassert>
    450 #include <vector>
    451 #include <algorithm>
    452  
    453 #define debug(x) #x << " = " << x << '\n'
    454  
    455 using ll = long long;
    456 #define YES std::cout << "YES\n"
    457 #define NO std::cout << "NO\n"
    458  
    459 void solve() {
    460   int n;
    461   std::cin >> n;
    462  
    463   std::string s;
    464   std::cin >> s;
    465  
    466 if (s  == "))))))))") {
    467     std::cout << "(()(()))";
    468     return;
    469 }
    470   if (n % 2 == 1) {
    471     std::cout << -1;
    472     return;
    473   }
    474   
    475   int delta = 0;
    476  
    477   assert((int) s.size() == n);
    478  
    479   for (int i = 0; i < (int) s.size(); i++) {
    480     int value = (s[i] == '('? +1 : -1);
    481     if (i & 1) {
    482       value *= -1;
    483     }
    484     delta += value;
    485   }
    486  
    487   if (delta == -n || std::abs(delta) % 4 != n % 4) {
    488     std::cout << -1;
    489     return;
    490   }
    491  
    492   int plus = (n + delta) / 2;
    493   int minus = (n - delta) / 2;
    494  
    495   assert(minus % 2 == 0);
    496  
    497   std::cout << "(";
    498   for (int i = 0; i < minus / 2; i++) {
    499     std::cout << "()";
    500   }
    501   std::cout << ")";
    502   for (int i = 0; i < (plus - 2) / 2; i++) {
    503     std::cout << "()";
    504   }
    505 }
    506  
    507 int main() {
    508   std::ios_base::sync_with_stdio(false);
    509   std::cin.tie(0);
    510  
    511   int t;
    512   std::cin >> t;
    513   for (int tc = 1; tc <= t; tc++) {
    514     std::cerr << "Case #" << tc << ":\n";
    515     solve();
    516     std::cout << '\n';
    517   }
    518  
    519   return 0;
    520 }
    521 ```
    522 
    523 [2143F - Увеличение XOR](/contest/2143/problem/F "Codeforces Round 1051 (Div. 2)")
    524 
    525 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Editorial: [MateiKing80](/profile/MateiKing80 "Мастер MateiKing80")
    526 
    527 **Solution**
    528 
    529 Tutorial is loading...
    530 
    531 **Code**
    532 
    533 ```
    534 #include <iostream>
    535 #include <cassert>
    536 #include <vector>
    537 #include <algorithm>
    538  
    539 #define debug(x) #x << " = " << x << '\n'
    540  
    541 using ll = long long;
    542 #define YES std::cout << "YES\n"
    543 #define NO std::cout << "NO\n"
    544  
    545 const int B = 21;
    546  
    547 struct XorBasis {
    548   std::vector<int> basis;
    549   std::vector<int> who;
    550   
    551   int sz;
    552  
    553   void reset() {
    554     basis.assign(B, 0);
    555     who.clear();
    556     sz = 0;
    557   }
    558  
    559   bool add(int x, int index) {
    560     for (int i = B - 1; i >= 0; i--) {
    561       if (x >> i & 1) {
    562         if (!basis[i]) {
    563           basis[i] = x;
    564           who.push_back(index);
    565           sz++;
    566           return true;
    567         }
    568         x ^= basis[i];
    569       }
    570     }
    571     return false;
    572   }
    573  
    574   int kth(int k) { // al k-lea cel mai mic subset xor 
    575     if (k < 1 || k > (1 << sz)) {
    576       return -1;
    577     }
    578     int x = 0;
    579     int cnt = (1 << sz);
    580     for (int i = B - 1; i >= 0; i--) {
    581       if (basis[i]) {
    582         if (k > cnt / 2) {
    583           if (!(x >> i & 1)) {
    584             x ^= basis[i];
    585           }
    586           // il fac sa fie 1
    587           k -= cnt / 2;
    588         } else {
    589           // il fac sa fie 0
    590           if (x >> i & 1) {
    591             x ^= basis[i];
    592           }
    593         }
    594         cnt /= 2;
    595       }
    596     }
    597     return x;
    598   }
    599  
    600   int count_le(int x) { // cate subset uri au xor < x?
    601     if (x < 0) {
    602       return 0;
    603     }
    604     int ret = 0;
    605     int cnt = (1 << sz);
    606     int mask = 0;
    607     for (int i = B - 1; i >= 0; i--) {
    608       if (basis[i]) {
    609         if (x >> i & 1) {
    610           ret += cnt / 2;
    611           if (!(mask >> i & 1)) {
    612             mask ^= basis[i];
    613           }
    614         } else {
    615           if (mask >> i & 1) {
    616             mask ^= basis[i];
    617           }
    618         }
    619         cnt /= 2;
    620       } else {
    621         if ((x ^ mask) >> i & 1) {
    622           if (x >> i & 1) {
    623             return ret + cnt;
    624           } else {
    625             return ret; 
    626           }
    627         }
    628       }
    629     }
    630     return ret;
    631   }
    632   int count_leq(int x) { // <= x
    633     return count_le(x + 1);
    634   }
    635   int jumpK(int value, int k) {
    636     int p = count_leq(value);
    637     return kth(p + k);
    638   }
    639 };
    640  
    641 int main() {
    642   #ifdef LOCAL
    643 freopen("input.txt", "r", stdin);
    644   #endif
    645   std::ios_base::sync_with_stdio(false);
    646   std::cin.tie(0);
    647   std::cout.tie(0);
    648  
    649 int tc;
    650 std::cin >> tc;
    651 while (tc--) {
    652   int n, q;
    653   std::cin >> n >> q;
    654   std::vector<int> a(n);
    655   for (int &x : a) {
    656     std::cin >> x;
    657   }
    658   
    659   XorBasis B;
    660   B.reset();
    661  
    662   std::vector<int> maxR(n);
    663  
    664   for (int l = n - 1; l >= 0; l--) {
    665     if (!B.add(a[l], l)) {
    666       std::vector<int> ids = B.who;
    667       ids.push_back(l);
    668       std::sort(ids.begin(), ids.end());
    669       B.reset();
    670       for (int index : ids) {
    671         B.add(a[index], index);
    672       }
    673     } 
    674  
    675     std::sort(B.who.begin(), B.who.end());
    676  
    677     XorBasis aux;
    678     aux.reset();
    679     std::swap(B, aux);
    680  
    681     int r = n - 1;
    682  
    683     int maxExtend = l;
    684     int prevIndex = l - 1;
    685     int prevValue = -1;
    686     
    687     for (int index : aux.who) {
    688       if (index - 1 > maxExtend) {
    689         r = std::min(r, maxExtend);
    690         break;
    691       }
    692       int before = (prevValue == -1? -1 : B.jumpK(prevValue, index - 1 - prevIndex));
    693       B.add(a[index], index);
    694       int me = B.jumpK(before, 1);
    695       if (me == -1) {
    696         r = std::min(r, index - 1);
    697         break;
    698       }
    699       maxExtend = index + (1 << B.sz) - B.count_leq(me); 
    700       prevValue = me;
    701       prevIndex = index;
    702     }
    703     r = std::min(r, maxExtend);
    704  
    705     std::swap(aux, B);
    706     maxR[l] = r;
    707   }
    708  
    709   while (q--) {
    710     int l, r;
    711     std::cin >> l >> r;
    712     l--, r--;
    713     if (r <= maxR[l]) {
    714       YES;
    715     } else {
    716       NO;
    717     }
    718   }
    719 }
    720  
    721   return 0;
    722 }
    723 ```