codeforces-scrape

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

1418.md (11260B)


      1 Source: https://codeforces.com/blog/entry/82673
      2 
      3 [1418A - Buying Torches](/contest/1418/problem/A "Educational Codeforces Round 95 (Rated for Div. 2)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Master vovuh")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (vovuh)**
     12 
     13 ```
     14 for i in range(int(input())):
     15     x, y, k = map(int, input().split())
     16     print(((y + 1) * k - 1 + x - 2) // (x - 1) + k)
     17 ```
     18 
     19 [1418B - Negative Prefixes](/contest/1418/problem/B "Educational Codeforces Round 95 (Rated for Div. 2)")
     20 
     21 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 **Solution (Ne0n25)**
     28 
     29 ```
     30 #include <bits/stdc++.h>
     31 
     32 using namespace std;
     33 
     34 #define sz(a) int((a).size())
     35 #define forn(i, n) for (int i = 0; i < int(n); ++i)
     36 
     37 void solve() {
     38     int n;
     39     cin >> n;
     40     vector<int> a(n), b(n), c;
     41     forn(i, n) cin >> a[i];
     42     forn(i, n) cin >> b[i];
     43     forn(i, n) if (!b[i])
     44         c.push_back(a[i]);
     45     sort(c.rbegin(), c.rend());
     46     int j = 0;
     47     forn(i, n) {
     48         if (b[i]) cout << a[i] << ' ';
     49         else cout << c[j++] << ' ';
     50     }
     51     cout << '\n';
     52 }
     53 
     54 int main() {
     55     int T;
     56     cin >> T;
     57     while (T--) solve();
     58 }
     59 ```
     60 
     61 [1418C - Mortal Kombat Tower](/contest/1418/problem/C "Educational Codeforces Round 95 (Rated for Div. 2)")
     62 
     63 Idea: [vovuh](/profile/vovuh "Master vovuh")
     64 
     65 **Tutorial**
     66 
     67 Tutorial is loading...
     68 
     69 **Solution (vovuh)**
     70 
     71 ```
     72 #include <bits/stdc++.h>
     73 
     74 using namespace std;
     75 
     76 int main() {
     77 #ifdef _DEBUG
     78     freopen("input.txt", "r", stdin);
     79 //  freopen("output.txt", "w", stdout);
     80 #endif
     81     
     82     int t;
     83     cin >> t;
     84     while (t--) {
     85         int n;
     86         cin >> n;
     87         vector<int> a(n);
     88         for (auto &it : a) cin >> it;
     89         int ans = 0;
     90         ans += a[0] == 1;
     91         for (int i = 1; i < n; ++i) {
     92             if (a[i] == 0) {
     93                 continue;
     94             }
     95             int j = i;
     96             while (j < n && a[j] == 1) {
     97                 ++j;
     98             }
     99             ans += (j - i) / 3;
    100             i = j - 1;
    101         }
    102         cout << ans << endl;
    103     }
    104     
    105     return 0;
    106 }
    107 ```
    108 
    109 [1418D - Trash Problem](/contest/1418/problem/D "Educational Codeforces Round 95 (Rated for Div. 2)")
    110 
    111 Idea: [vovuh](/profile/vovuh "Master vovuh")
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...
    116 
    117 **Solution (vovuh)**
    118 
    119 ```
    120 #include <bits/stdc++.h>
    121 
    122 using namespace std;
    123 
    124 int get(const set<int> &x, const multiset<int> &len) {
    125     if (len.empty()) return 0;
    126     return *x.rbegin() - *x.begin() - *len.rbegin();
    127 }
    128 
    129 void add(int p, set<int> &x, multiset<int> &len) {
    130     x.insert(p);
    131     auto it = x.find(p);
    132     int prv = -1, nxt = -1;
    133     if (it != x.begin()) {
    134         --it;
    135         len.insert(p - *it);
    136         prv = *it;
    137         ++it;
    138     }
    139     ++it;
    140     if (it != x.end()) {
    141         len.insert(*it - p);
    142         nxt = *it;
    143     }
    144     if (prv != -1 && nxt != -1) {
    145         len.erase(len.find(nxt - prv));
    146     }
    147 }
    148 
    149 void rem(int p, set<int> &x, multiset<int> &len) {
    150     auto it = x.find(p);
    151     int prv = -1, nxt = -1;
    152     if (it != x.begin()) {
    153         --it;
    154         len.erase(len.find(p - *it));
    155         prv = *it;
    156         ++it;
    157     }
    158     ++it;
    159     if (it != x.end()) {
    160         len.erase(len.find(*it - p));
    161         nxt = *it;
    162     }
    163     x.erase(p);
    164     if (prv != -1 && nxt != -1) {
    165         len.insert(nxt - prv);
    166     }
    167 }
    168 
    169 int main() {
    170 #ifdef _DEBUG
    171     freopen("input.txt", "r", stdin);
    172 //  freopen("output.txt", "w", stdout);
    173 #endif
    174     
    175     int n, q;
    176     cin >> n >> q;
    177     set<int> x;
    178     multiset<int> len;
    179     for (int i = 0; i < n; ++i) {
    180         int p;
    181         cin >> p;
    182         add(p, x, len);
    183     }
    184     
    185     cout << get(x, len) << endl;
    186     for (int i = 0; i < q; ++i) {
    187         int t, p;
    188         cin >> t >> p;
    189         if (t == 0) {
    190             rem(p, x, len);
    191         } else {
    192             add(p, x, len);
    193         }
    194         cout << get(x, len) << endl;
    195     }
    196     
    197     return 0;
    198 }
    199 ```
    200 
    201 [1418E - Expected Damage](/contest/1418/problem/E "Educational Codeforces Round 95 (Rated for Div. 2)")
    202 
    203 Idea: [Roms](/profile/Roms "Master Roms")
    204 
    205 **Tutorial**
    206 
    207 Tutorial is loading...
    208 
    209 **Solution (Roms)**
    210 
    211 ```
    212 #include <bits/stdc++.h>
    213 
    214 using namespace std;
    215 
    216 const int N = int(2e5) + 9;
    217 const int MOD = 998244353;
    218 
    219 int mul(int a, int b) {
    220     return (a * 1LL * b) % MOD;
    221 }
    222 
    223 int bp(int a, int n) {
    224     int res = 1;
    225     for (; n > 0; n /= 2) {
    226         if (n & 1) res = mul(res, a);
    227         a = mul(a, a);
    228     }
    229     
    230     return res;
    231 }
    232 
    233 int inv(int a) {
    234     int ia = bp(a, MOD - 2);
    235     assert(mul(a, ia) == 1);
    236     return ia;
    237 }
    238 
    239 int n, m;
    240 int d[N];
    241 long long sd[N];
    242 
    243 long long sum (int l, int r) {
    244     return (sd[r] - sd[l]) % MOD;
    245 }
    246 
    247 int main(){
    248     cin >> n >> m;
    249     for (int i = 0; i < n; ++i)
    250         scanf("%d", d + i);
    251     sort(d, d + n);
    252     for (int i = 0; i < n; ++i)
    253         sd[i + 1] = sd[i] + d[i];
    254         
    255     for (int i = 0; i < m; ++i) {
    256         int a, b;
    257         scanf("%d%d", &a, &b); // dur, def
    258         int cnt = (d + n) - lower_bound(d, d + n, b);
    259         int res = 0;
    260         if (cnt >= a) {
    261             res = mul( mul(cnt - a, inv(cnt)), sum(n - cnt, n) );
    262             res += mul( mul(cnt - a + 1, inv(cnt + 1)), sum(0, n - cnt) );
    263             res %= MOD;
    264         }
    265         printf("%d\n", res);
    266     }
    267     
    268     return 0;
    269 }
    270 ```
    271 
    272 [1418F - Equal Product](/contest/1418/problem/F "Educational Codeforces Round 95 (Rated for Div. 2)")
    273 
    274 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    275 
    276 **Tutorial**
    277 
    278 Tutorial is loading...
    279 
    280 **Solution (adedalic)**
    281 
    282 ```
    283 #include<bits/stdc++.h>
    284 
    285 using namespace std;
    286 
    287 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    288 #define sz(a) int((a).size())
    289 
    290 #define x first
    291 #define y second
    292 
    293 typedef long long li;
    294 typedef pair<int, int> pt;
    295 
    296 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    297     return out << "(" << p.x << ", " << p.y << ")";
    298 }
    299 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    300     out << "[";
    301     fore(i, 0, sz(v)) {
    302         if(i) out << ", ";
    303         out << v[i];
    304     }
    305     return out << "]";
    306 }
    307 
    308 const int INF = int(1e9);
    309 const li INF64 = li(1e18);
    310 
    311 int n, m;
    312 li l, r;
    313 
    314 inline bool read() {
    315     if(!(cin >> n >> m))
    316         return false;
    317     cin >> l >> r;
    318     return true;
    319 }
    320 
    321 const int N = int(2e5) + 555;
    322 vector<int> divs[N];
    323 
    324 inline void solve() {
    325     fore(d, 1, N) {
    326         for(int pos = d; pos < N; pos += d)
    327             divs[pos].push_back(d);
    328     }
    329     
    330     li lf = m + 1, rg = m;
    331     vector<int> cnt(m + 1, 0);
    332     vector<int> id(m + 1, -1);
    333     set<int> curDivs;
    334     
    335     vector< vector<int> > ans(n + 1);
    336     
    337     fore(x1, 1, n + 1) {
    338         li newlf = (l + x1 - 1) / x1;
    339         li newrg = r / x1;
    340         assert(newrg - newlf + 1 >= 0);
    341         
    342         while (lf > newlf) {
    343             lf--;
    344             for (int d : divs[lf]) {
    345                 if (cnt[d] == 0)
    346                     curDivs.insert(d);
    347                 cnt[d]++;
    348                 id[d] = (int)lf;
    349             }
    350         }
    351         while (rg > newrg) {
    352             for (int d : divs[rg]) {
    353                 cnt[d]--;
    354                 if (cnt[d] == 0)
    355                     curDivs.erase(d);
    356             }
    357             rg--;
    358         }
    359         
    360         for (int a : divs[x1]) {
    361             auto it = curDivs.upper_bound(a);
    362             if (it == curDivs.end())
    363                 continue;
    364             
    365             int b = *it;
    366             if (x1 / a * 1ll * b <= n) {
    367                 int y1 = id[b];
    368                 
    369                 ans[x1] = {x1, y1, x1 / a * b, y1 / b * a};
    370             }
    371         }
    372     }
    373     
    374     fore(i, 1, n + 1) {
    375         if (ans[i].empty())
    376             cout << -1 << '\n';
    377         else {
    378             cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << '\n';
    379         }
    380     }
    381 }
    382 
    383 int main() {
    384 #ifdef _DEBUG
    385     freopen("input.txt", "r", stdin);
    386     int tt = clock();
    387 #endif
    388     ios_base::sync_with_stdio(false);
    389     cin.tie(0), cout.tie(0);
    390     cout << fixed << setprecision(15);
    391     
    392     if(read()) {
    393         solve();
    394         
    395 #ifdef _DEBUG
    396         cerr << "TIME = " << clock() - tt << endl;
    397         tt = clock();
    398 #endif
    399     }
    400     return 0;
    401 }
    402 ```
    403 
    404 [1418G - Three Occurrences](/contest/1418/problem/G "Educational Codeforces Round 95 (Rated for Div. 2)")
    405 
    406 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") and [Roms](/profile/Roms "Master Roms")
    407 
    408 **Tutorial**
    409 
    410 Tutorial is loading...
    411 
    412 **Solution 1 (pikmike)**
    413 
    414 ```
    415 #include <bits/stdc++.h>
    416  
    417 using namespace std;
    418 
    419 #define forn(i, n) for(int i = 0; i < int(n); i++)
    420 
    421 const int N = 60;
    422 
    423 typedef array<int, N> num;
    424 
    425 num operator ^(const num &a, const num &b){
    426     num c;
    427     forn(i, N){
    428         c[i] = a[i] + b[i];
    429         if (c[i] >= 3) c[i] -= 3;
    430     }
    431     return c;
    432 }
    433 
    434 mt19937 rnd(42);
    435 
    436 int main(){
    437     int n;
    438     scanf("%d", &n);
    439     vector<int> a(n);
    440     forn(i, n){
    441         scanf("%d", &a[i]);
    442         --a[i];
    443     }
    444     
    445     vector<num> nums(n);
    446     forn(i, n) forn(j, N) nums[i][j] = rnd() % 3;
    447     
    448     vector<vector<int>> pos(n);
    449     vector<num> pr(1);
    450     map<num, int> cnt;
    451     cnt[pr[0]] = 1;
    452     int cur = 0;
    453     long long ans = 0;
    454     forn(i, n){
    455         pr.push_back(pr.back() ^ nums[a[i]]);
    456         pos[a[i]].push_back(i);
    457         if (pos[a[i]].size() >= 4){
    458             while (cur <= pos[a[i]][int(pos[a[i]].size()) - 4]){
    459                 --cnt[pr[cur]];
    460                 ++cur;
    461             }
    462         }
    463         ans += cnt[pr.back()];
    464         ++cnt[pr.back()];
    465     }
    466     
    467     printf("%lld\n", ans);
    468 }
    469 ```
    470 
    471 **Solution 2 (pikmike)**
    472 
    473 ```
    474 #include <bits/stdc++.h>
    475  
    476 using namespace std;
    477 
    478 #define forn(i, n) for(int i = 0; i < int(n); i++)
    479 
    480 typedef unsigned long long uli;
    481 
    482 vector<int> a;
    483 vector<pair<int, int>> t;
    484 vector<int> ps;
    485 
    486 pair<int, int> merge(const pair<int, int> &a, const pair<int, int> &b){
    487     if (a.first != b.first)
    488         return min(a, b);
    489     return make_pair(a.first, a.second + b.second);
    490 }
    491 
    492 void push(int v){
    493     if (v * 2 + 1 < int(ps.size())){
    494         ps[v * 2] += ps[v];
    495         ps[v * 2 + 1] += ps[v];
    496     }
    497     t[v].first += ps[v];
    498     ps[v] = 0;
    499 }
    500 
    501 void build(int v, int l, int r){
    502     if (l == r - 1){
    503         t[v] = make_pair(0, 1);
    504         return;
    505     }
    506     int m = (l + r) / 2;
    507     build(v * 2, l, m);
    508     build(v * 2 + 1, m, r);
    509     t[v] = merge(t[v * 2], t[v * 2 + 1]);
    510 }
    511 
    512 void upd(int v, int l, int r, int L, int R, int val){
    513     push(v);
    514     if (L >= R)
    515         return;
    516     if (l == L && r == R){
    517         ps[v] = val;
    518         push(v);
    519         return;
    520     }
    521     int m = (l + r) / 2;
    522     upd(v * 2, l, m, L, min(m, R), val);
    523     upd(v * 2 + 1, m, r, max(m, L), R, val);
    524     t[v] = merge(t[v * 2], t[v * 2 + 1]);
    525 }
    526 
    527 int main(){
    528     int n;
    529     scanf("%d", &n);
    530     a.resize(n);
    531     forn(i, n){
    532         scanf("%d", &a[i]);
    533         --a[i];
    534     }
    535     t.resize(4 * n);
    536     ps.resize(4 * n);
    537     build(1, 0, n);
    538     vector<vector<int>> pos(n, vector<int>(1, -1));
    539     long long ans = 0;
    540     forn(i, n){
    541         int k = pos[a[i]].size();
    542         if (k >= 1) upd(1, 0, n, pos[a[i]][k - 1] + 1, i + 1, 1);
    543         if (k >= 3) upd(1, 0, n, pos[a[i]][k - 3] + 1, pos[a[i]][k - 2] + 1, -1);
    544         if (k >= 4) upd(1, 0, n, pos[a[i]][k - 4] + 1, pos[a[i]][k - 3] + 1, 1);
    545         pos[a[i]].push_back(i);
    546         push(1);
    547         if (t[1].first == 0) ans += t[1].second - (n - i - 1);
    548     }
    549     printf("%lld\n", ans);
    550 }
    551 ```