codeforces-scrape

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

2126.md (10013B)


      1 Source: https://codeforces.com/blog/entry/144845
      2 
      3 [2126A - Only One Digit](/contest/2126/problem/A "Codeforces Round 1037 (Div. 3)")
      4 
      5 Idea: [soullless](/profile/soullless "Master soullless")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 using namespace std;
     16 int main() {
     17   int t;
     18   cin >> t;
     19   while(t--) {
     20     int x;
     21     cin >> x;
     22     int mn = 9;
     23     while(x > 0) {
     24       mn = min(mn, x % 10);
     25       x/=10;
     26     }
     27     cout << mn << endl;
     28   }
     29 }
     30 ```
     31 
     32 [2126B - No Casino in the Mountains](/contest/2126/problem/B "Codeforces Round 1037 (Div. 3)")
     33 
     34 Idea: [soullless](/profile/soullless "Master soullless")
     35 
     36 **Tutorial**
     37 
     38 Tutorial is loading...
     39 
     40 **Solution**
     41 
     42 ```
     43 #include <bits/stdc++.h>
     44 using namespace std;
     45 int main() {
     46   int t;
     47   cin >> t;
     48   while(t--) {
     49     int n,k;
     50     cin >> n >> k;
     51     int a[n + 1];
     52     for(int i = 1;i <= n;i++) cin >> a[i];
     53     int ans = 0;
     54     int cnt = 0;
     55     for(int i = 1;i <= n;i++) {
     56       if(a[i] == 1) {
     57         ans+=(cnt + 1)/(k + 1);
     58         cnt = 0;
     59         continue;
     60       }
     61       else {
     62         cnt++;
     63       }
     64     }
     65     ans+=(cnt + 1)/(k + 1);
     66     cout << ans << endl;
     67   }
     68 }
     69 ```
     70 
     71 [2126C - I Will Definitely Make It](/contest/2126/problem/C "Codeforces Round 1037 (Div. 3)")
     72 
     73 Idea: [soullless](/profile/soullless "Master soullless")
     74 
     75 **Tutorial**
     76 
     77 Tutorial is loading...
     78 
     79 **Solution**
     80 
     81 ```
     82 #include <bits/stdc++.h>
     83 using namespace std;
     84 int main() {
     85   int t;
     86   cin >> t;
     87   while(t--) {
     88     int n,p;
     89     cin >> n >> p;
     90     int a[n + 1];
     91     for(int i = 1;i <= n;i++) cin >> a[i];
     92     int cur = a[p];
     93     int dist = a[p];
     94     sort(a + 1,a + n + 1);
     95     bool ans = true;
     96     for(int i = 1;i <= n;i++) {
     97       if(a[i] < cur) continue;
     98       if(a[i] &mdash; cur > dist) {
     99         ans = false;
    100       }
    101       cur = a[i];
    102     }
    103     if(ans) cout << "YES" << endl;
    104     else cout << "NO" << endl;
    105   }
    106 }
    107 ```
    108 
    109 [2126D - This Is the Last Time](/contest/2126/problem/D "Codeforces Round 1037 (Div. 3)")
    110 
    111 Idea: [soullless](/profile/soullless "Master soullless")
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...
    116 
    117 **Solution**
    118 
    119 ```
    120 #include <bits/stdc++.h>
    121 using namespace std;
    122 int main() {
    123   int t;
    124   cin >> t;
    125   while(t--) {
    126     int n,k;
    127     cin >> n >> k;
    128     pair <int,pair <int,int> > p[n + 1];
    129     for(int i = 1;i <= n;i++) cin >> p[i].first >> p[ыi].second.first >> p[i].second.second;
    130     sort(p + 1,p + n + 1);
    131     int cur = k;
    132     for(int i = 1;i <= n;i++) {
    133       if(p[i].first > cur) break;
    134       cur = max(cur,p[i].second.second);
    135     }
    136     cout << cur << endl;
    137   }
    138 }
    139 ```
    140 
    141 [2126E - G-C-D, Unlucky!](/contest/2126/problem/E "Codeforces Round 1037 (Div. 3)")
    142 
    143 Idea: [Away_in_the_heavens](/profile/Away_in_the_heavens "Expert Away_in_the_heavens")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution**
    150 
    151 ```
    152 #include <bits/stdc++.h>
    153 using namespace std;
    154 main() {
    155     int t;
    156     cin >> t;
    157     while (t--) {
    158         int n;
    159         cin >> n;
    160         long long a[n + 1];
    161         for (int i = 1; i <= n; i++) {
    162             cin >> a[i];
    163         }
    164         long long b[n + 1];
    165         for (int i = 1; i <= n; i++) {
    166             cin >> b[i];
    167         }
    168         long long ans[n + 1];
    169         for (int i = n; i >= 1; i--) {
    170             ans[i] = lcm(a[i], b[i]);
    171         }
    172         bool ch = 1;
    173         if(ans[1] != a[1]) ch = 0;
    174         if(ans[n] != b[n]) ch = 0;
    175         for (int i = 2; i <= n; i++) {
    176             if (__gcd(a[i &mdash; 1], ans[i]) != a[i]) {
    177                 ch = 0;
    178             }
    179         }
    180         for (int i = n &mdash; 1; i >= 1; i--) {
    181             if (__gcd(b[i + 1], ans[i]) != b[i]) {
    182                 ch = 0;
    183             }
    184         }
    185         if (ch) {
    186             cout << "YES" << "\n";
    187         } else {
    188             cout << "NO" << "\n";
    189         }
    190     }
    191 }
    192 ```
    193 
    194 [2126F - 1-1-1, Free Tree!](/contest/2126/problem/F "Codeforces Round 1037 (Div. 3)")
    195 
    196 Idea: [soullless](/profile/soullless "Master soullless")
    197 
    198 **Tutorial**
    199 
    200 Tutorial is loading...
    201 
    202 **Solution**
    203 
    204 ```
    205 #include <bits/stdc++.h>
    206 using namespace std;
    207 const int B = 2e5 + 100;
    208 int n;
    209 int col[B];
    210 long long costt = 0;
    211 vector <pair <int,int> > reb[B];
    212 bool was[B];
    213 map <int,long long> cnt[B];
    214 int pred[B];
    215 long long zn[B];
    216 void dfs(int v) {
    217   was[v] = true;
    218   for(auto u:reb[v]) {
    219     if(was[u.first]) {
    220       pred[v] = u.first;
    221       continue;
    222     }
    223     if(col[v] != col[u.first]) costt+=u.second;
    224     dfs(u.first);
    225     zn[u.first] = u.second;
    226     cnt[v][col[u.first]]+=zn[u.first];
    227   }
    228 }
    229 void update(int v,int x) {
    230   if(v != 1) {
    231     cnt[pred[v]][col[v]]-=zn[v];
    232     if(col[pred[v]] == col[v]) costt+=zn[v];
    233     cnt[pred[v]][x]+=zn[v];
    234     if(col[pred[v]] == x) costt-=zn[v];
    235   }
    236   else {
    237       
    238   }
    239   costt+=cnt[v][col[v]];
    240   costt-=cnt[v][x];
    241   col[v] = x;
    242 }
    243 void clr() {
    244   for(int i = 1;i <= n;i++) {
    245     reb[i].clear();
    246     was[i] = false;
    247     cnt[i].clear();
    248     zn[i] = 0;
    249   }
    250   costt = 0;
    251 }
    252 int main() {
    253   int t;
    254   cin >> t;
    255   while(t--) {
    256     int q;
    257     cin >> n >> q;
    258     for(int i = 1; i <= n; i++) cin >> col[i];
    259     for(int i = 1; i < n; i++) {
    260       int u, v, c;
    261       cin >> u >> v >> c;
    262       reb[v].push_back({u,c});
    263       reb[u].push_back({v,c});
    264     }
    265     dfs(1);
    266     while(q--) {
    267       int pos,x;
    268       cin >> pos >> x;
    269       update(pos,x);
    270       cout << costt << "\n";
    271     }
    272     clr();
    273   }
    274 }
    275 ```
    276 
    277 [2126G1 - Big Wins! (easy version)](/contest/2126/problem/G1 "Codeforces Round 1037 (Div. 3)")
    278 
    279 Idea: [soullless](/profile/soullless "Master soullless")
    280 
    281 **Tutorial**
    282 
    283 Tutorial is loading...
    284 
    285 **Solution**
    286 
    287 ```
    288 #include <bits/stdc++.h>
    289 using namespace std;
    290 const int B = 2e5 + 100;
    291 
    292 int main() {
    293   int t;
    294   cin >> t;
    295   while(t--) {
    296     int n;
    297     cin >> n;
    298     int a[n + 1];
    299     for(int i = 1;i <= n;i++) cin >> a[i];
    300     int ans = 0;
    301     for(int i = 1;i <= 100;i++) {
    302       int b[n + 1] = {};
    303       for(int j = 1;j <= n;j++) {
    304         if(a[j] >= i) b[j] = 1;
    305         else b[j] = -1;
    306       }
    307       int pref[n + 1] = {};
    308       for(int j = 1; j <= n; j++) {
    309         pref[j] = pref[j - 1] + b[j]; 
    310       }
    311       int prefmn[n + 2] = {},suffmx[n + 1] = {};
    312       prefmn[0] = 0,suffmx[n] = pref[n];
    313       for(int j = 1; j <= n; j++) {
    314         prefmn[j] = min(prefmn[j - 1],pref[j]);
    315       }
    316       for(int j = n - 1; j >= 1; j--) {
    317         suffmx[j] = max(suffmx[j + 1],pref[j]);
    318       }
    319       for(int j = 1; j <= n; j++) {
    320         if(prefmn[j - 1] <= pref[j] || pref[j - 1] <= suffmx[j]) {
    321           ans = max(ans,i - a[j]);
    322         }
    323       }
    324     } 
    325     cout << ans << endl;
    326   }
    327 }
    328 ```
    329 
    330 [2126G2 - Big Wins! (hard version)](/contest/2126/problem/G2 "Codeforces Round 1037 (Div. 3)")
    331 
    332 Idea: [soullless](/profile/soullless "Master soullless")
    333 
    334 **Tutorial**
    335 
    336 Tutorial is loading...
    337 
    338 **Solution**
    339 
    340 ```
    341 #include<bits/stdc++.h>
    342 using namespace std;
    343 int n;
    344 int a[200005 + 2];
    345 array<int, 4> t[800005];
    346 array<int, 4> merge(array<int, 4>a, array<int, 4>b) {
    347     int ans = max(a[0], b[0]);
    348     int mxpref = max(a[1], a[3] + b[1]);
    349     int mxsuff = max(b[2], a[2] + b[3]);
    350     ans = max({ans, mxpref, mxsuff});
    351     int sum = a[3] + b[3];
    352     return {ans, mxpref, mxsuff, sum};
    353 }
    354 void update(int v, int tl, int tr, int pos, int val) {
    355     if (tl == tr) {
    356         t[v] = {max(val, 0), max(val, 0), max(val, 0), val};
    357     } else {
    358         int tm = (tl + tr) >> 1;
    359         if (pos <= tm) {
    360             update(v * 2, tl, tm, pos, val);
    361         } else {
    362             update(v * 2 + 1, tm + 1, tr, pos, val);
    363         }
    364         t[v] = merge(t[v * 2], t[v * 2 + 1]);
    365     }
    366 }
    367 array<int, 4> get(int v, int tl, int tr, int l, int r) {
    368     if (tl == l && tr == r) {
    369         return t[v];
    370     } else if (l > r) {
    371         return {0, 0, 0, 0};
    372     } else {
    373         int tm = (tl + tr) >> 1;
    374         return merge(get(v * 2, tl, tm, l, min(r, tm)), get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
    375     }
    376 }
    377 int solve(int n, vector<int>A) {
    378     int m = 0;
    379     for (int i = 1; i <= n; i++) {
    380         a[i] = A[i &mdash; 1];
    381         m = max(m, a[i]);
    382     }
    383     vector<int>ind[m + 1];
    384     for (int i = 1; i <= n; i++) {
    385         ind[a[i]].push_back(i);
    386     }
    387     stack<int>s;
    388     s.push(0);
    389     a[0] = -INT_MAX;
    390     int l[n + 1];
    391     for (int i = 1; i <= n; i++) {
    392         while (a[s.top()] >= a[i]) {
    393             s.pop();
    394         }
    395         l[i] = s.top() + 1;
    396         s.push(i);
    397     }
    398     a[n + 1] = -INT_MAX;
    399     s.push(n + 1);
    400     int r[n + 1];
    401     for (int i = n; i >= 1; i--) {
    402         while (a[s.top()] >= a[i]) {
    403             s.pop();
    404         }
    405         r[i] = s.top() &mdash; 1;
    406         s.push(i);
    407     }
    408     int med = 1;
    409     for (int i = 1; i <= n; i++) {
    410         update(1, 1, n, i, 1);
    411     }
    412     for (auto u : ind[1]) {
    413         update(1, 1, n, u, -1);
    414     }
    415     int ans = 0;
    416     for (int mn = 1; mn <= m; mn++) {
    417         for (auto u : ind[mn]) {
    418             int lg = l[u], rg = r[u];
    419             while (med < m && get(1, 1, n, lg, u &mdash; 1)[2] + get(1, 1, n, u + 1, rg)[1] + (a[u] < (med) ? -1 : 1) >= 0) {
    420                 med++;
    421                 for (auto u : ind[med]) {
    422                     update(1, 1, n, u, -1);
    423                 }
    424             }
    425         }
    426         // cout << med << ' ' << mn << endl;
    427         ans = max(ans, med &mdash; mn);
    428     }
    429     return ans;
    430 }
    431 int solveslow(int n, vector<int>A) {
    432     for (int i = 1; i <= n; i++) {
    433         a[i] = A[i &mdash; 1];
    434     }
    435     int mx = 0;
    436     for (int i = 1; i <= n; i++) {
    437         vector<int>v;
    438         for (int j = i; j <= n; j++) {
    439             v.push_back(a[j]);
    440             sort(v.begin(), v.end());
    441             mx = max(mx, v[v.size() / 2] &mdash; v[0]);
    442         }
    443     }
    444     return mx;
    445 }
    446 int rnd() {
    447     return (rand() + rand() * RAND_MAX);
    448 }
    449 main() {
    450     ios_base::sync_with_stdio(false);
    451     cin.tie(0);
    452     int tt;
    453     cin >> tt;
    454     while(tt--) {
    455         int n;
    456         cin >> n;
    457         vector<int>v;
    458         for (int i = 1; i <= n; i++) {
    459             int x;
    460             cin >> x;
    461             v.push_back(x);
    462         }
    463         cout << solve(n, v) << endl;
    464         // cout << solveslow(n, v) << endl;
    465         for(int i = 0;i <= n*4;i++) {
    466             t[i][0] = 0;
    467             t[i][1] = 0;
    468             t[i][2] = 0;
    469             t[i][3] = 0;
    470         }
    471     }
    472 }
    473 ```