codeforces-scrape

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

1946.md (12757B)


      1 Source: https://codeforces.com/blog/entry/127439
      2 
      3 author: [dope](/profile/dope "Master dope"), developer: [dope](/profile/dope "Master dope")
      4 
      5 [1946A - Median of an Array](/contest/1946/problem/A "Codeforces Round 936 (Div. 2)")
      6 
      7 **Editorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using i64 = long long;
     17 
     18 void solve() {
     19     int n;
     20     std::cin >> n;
     21     std::vector<int> a(n);
     22     for (int i = 0; i < n; i++) {
     23         std::cin >> a[i];
     24     }
     25     std::sort(a.begin(), a.end());
     26     int p = (n + 1) / 2 - 1;
     27     int res = std::count(a.begin() + p, a.end(), a[p]);
     28     std::cout << res << "\n";
     29 }
     30 
     31 signed main() {
     32     std::ios::sync_with_stdio(false);
     33     std::cin.tie(nullptr);
     34 
     35     int t = 1;
     36     std::cin >> t;
     37 
     38     while (t--) {
     39         solve();
     40     }
     41 }
     42 ```
     43 
     44 author: [max0000561](/profile/max0000561 "Master max0000561"), developer: [yunetive29](/profile/yunetive29 "Candidate Master yunetive29")
     45 
     46 [1946B - Maximum Sum](/contest/1946/problem/B "Codeforces Round 936 (Div. 2)")
     47 
     48 **Editorial**
     49 
     50 Tutorial is loading...
     51 
     52 **Solution**
     53 
     54 ```
     55 #include <bits/stdc++.h>
     56 using namespace std;
     57 #define int long long
     58 const int P = 1e9 + 7;
     59 
     60 void solve() {
     61     int n, k;
     62     cin >> n >> k;
     63     vector<int> a(n);
     64     for (int i = 0; i < n; i++)
     65         cin >> a[i];
     66     int S = 0, sum = 0;
     67     int cur = 0;
     68     for (int i = 0; i < n; i++) {
     69         sum += a[i];
     70         cur += a[i];
     71         cur = max(cur, 0LL);
     72         S = max(S, cur);
     73     }
     74     sum = (sum % P + P) % P;
     75     S = S % P;
     76     int t = 1;
     77     for (int i = 0; i < k; i++) {
     78         t = t * 2 % P;
     79     }
     80     int ans = (sum + S * t - S + P) % P;
     81     cout << ans << '\n';
     82 }
     83 
     84 signed main() {
     85     //cout << fixed << setprecision(20);
     86     ios::sync_with_stdio(false);
     87     cin.tie(nullptr);
     88     int T = 1, G = 1;
     89     //cin >> G;
     90     cin >> T;
     91     while (T--)
     92         solve();
     93     return 0;
     94 }
     95 ```
     96 
     97 author: [dope](/profile/dope "Master dope"), developer: [dope](/profile/dope "Master dope")
     98 
     99 [1946C - Tree Cutting](/contest/1946/problem/C "Codeforces Round 936 (Div. 2)")
    100 
    101 **Editorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution**
    106 
    107 ```
    108 #include <bits/stdc++.h>
    109  
    110 using i64 = long long;
    111  
    112 void solve() {
    113     int n, k;
    114     std::cin >> n >> k;
    115     std::vector<std::vector<int>> adj(n);
    116     for (int i = 0; i < n - 1; i++) {
    117         int v, u;
    118         std::cin >> v >> u;
    119         --v, --u;
    120         adj[v].emplace_back(u);
    121         adj[u].emplace_back(v);
    122     }
    123     auto check = [&](int x) {
    124         int res = 0;
    125         auto dfs = [&](auto self, int v, int f) -> int {
    126             int sz = 1;
    127             for (int u : adj[v]) {
    128                 if (u == f) {
    129                     continue;
    130                 }
    131                 sz += self(self, u, v);
    132             }
    133             if (sz >= x && f != v) {
    134                 ++res, sz = 0;
    135             }
    136             return sz;
    137         };
    138         int t = dfs(dfs, 0, 0);
    139         return (res > k || (t >= x && res == k) ? true : false);
    140     };
    141     int low = 1, high = n / (k + 1) + 1;
    142     while (high - low > 1) {
    143         int mid = (low + high) / 2;
    144         if (check(mid)) {
    145             low = mid;
    146         } else {
    147             high = mid;
    148         }
    149     }
    150     std::cout << low << "\n";
    151 }
    152  
    153 signed main() {
    154     std::ios::sync_with_stdio(false);
    155     std::cin.tie(nullptr);
    156  
    157     int t = 1;
    158     std::cin >> t;
    159  
    160     while (t--) {
    161         solve();
    162     }
    163 }
    164 ```
    165 
    166 author: [sadness](/profile/sadness "Master sadness"), developer: [sadness](/profile/sadness "Master sadness")
    167 
    168 [1946D - Birthday Gift](/contest/1946/problem/D "Codeforces Round 936 (Div. 2)")
    169 
    170 **Editorial**
    171 
    172 Tutorial is loading...
    173 
    174 **Solution**
    175 
    176 ```
    177 #include <bits/stdc++.h>
    178  
    179 using namespace std;
    180  
    181 using ll = long long;
    182  
    183 #define int ll
    184 #define all(a) a.begin(), a.end()
    185  
    186 void solve() {
    187     int n, x;
    188     cin >> n >> x;
    189     ++x;
    190     vector<int> a(n);
    191     for (int &i: a)
    192         cin >> i;
    193     int res = -1;
    194     for (int i = 30; i >= 0; --i) {
    195         vector<int> b;
    196         bool open = false;
    197         for (int j = 0; j < a.size(); ++j) {
    198             if (!open)
    199                 b.push_back(a[j]);
    200             else
    201                 b.back() ^= a[j];
    202             if (a[j] & (1 << i))
    203                 open = !open;
    204         }
    205         if (!(x & (1 << i))) {
    206             if (open) {
    207                 cout << res << '\n';
    208                 return;
    209             }
    210             a = b;
    211         } else {
    212             if (!open)
    213                 res = max(res, (int) b.size());
    214         }
    215     }
    216     cout << res << '\n';
    217 }
    218  
    219 signed main() {
    220     ios_base::sync_with_stdio(false);
    221     cin.tie(nullptr);
    222     int t = 1;
    223     cin >> t;
    224     while (t--)
    225         solve();
    226 }
    227 ```
    228 
    229 **Solution (74TrAkToR)**
    230 
    231 ```
    232 #include<bits/stdc++.h>
    233  
    234 using namespace std;
    235  
    236 int const maxn = 1e5 + 5;
    237 int a[maxn];
    238  
    239 int solve(int n, int x) {
    240     int res = 0, curr = 0;
    241     for (int i = 1; i <= n; i++) {
    242         curr ^= a[i];
    243         if ((curr|x) == x) curr = 0, res++;
    244         else {
    245             if (i == n) return -1;
    246         }
    247     }
    248     return res;
    249 }
    250  
    251 main() {
    252     ios_base::sync_with_stdio(0);
    253     cin.tie(0);
    254     cout.tie(0);
    255     int t;
    256     cin >> t;
    257     while (t--) {
    258         int n, x;
    259         cin >> n >> x;
    260         for (int i = 1; i <= n; i++) cin >> a[i];
    261         int ans = -1;
    262         ans = max(ans, solve(n, x));
    263         for (int b = 29; b >= 0; b--) {
    264             if ((x>>b)&1) {
    265                 int y = (x^(1 << b));
    266                 for (int c = b - 1; c >= 0; c--) {
    267                     if (((y>>c)&1) == 0) y ^= (1 << c);
    268                 }
    269                 ans = max(ans, solve(n, y));
    270             }
    271         }
    272         cout << ans << '\n';
    273     }
    274     return 0;
    275 }
    276 ```
    277 
    278 author: [yunetive29](/profile/yunetive29 "Candidate Master yunetive29"), developer: [yunetive29](/profile/yunetive29 "Candidate Master yunetive29")
    279 
    280 [1946E - Girl Permutation](/contest/1946/problem/E "Codeforces Round 936 (Div. 2)")
    281 
    282 **Editorial**
    283 
    284 Tutorial is loading...
    285 
    286 **Solution**
    287 
    288 ```
    289 #include <bits/stdc++.h>
    290  
    291 using i64 = long long;
    292  
    293 template<class T>
    294 constexpr T power(T a, i64 b) {
    295     T res = 1;
    296     for (; b; b /= 2, a *= a) {
    297         if (b % 2) {
    298             res *= a;
    299         }
    300     }
    301     return res;
    302 }
    303  
    304 template<int P>
    305 struct MInt {
    306     int x;
    307     constexpr MInt() : x{} {}
    308     constexpr MInt(i64 x) : x{norm(x % P)} {}
    309     
    310     constexpr int norm(int x) const {
    311         if (x < 0) {
    312             x += P;
    313         }
    314         if (x >= P) {
    315             x -= P;
    316         }
    317         return x;
    318     }
    319     constexpr int val() const {
    320         return x;
    321     }
    322     explicit constexpr operator int() const {
    323         return x;
    324     }
    325     constexpr MInt operator-() const {
    326         MInt res;
    327         res.x = norm(P - x);
    328         return res;
    329     }
    330     constexpr MInt inv() const {
    331         assert(x != 0);
    332         return power(*this, P - 2);
    333     }
    334     constexpr MInt &operator*=(MInt rhs) {
    335         x = 1LL * x * rhs.x % P;
    336         return *this;
    337     }
    338     constexpr MInt &operator+=(MInt rhs) {
    339         x = norm(x + rhs.x);
    340         return *this;
    341     }
    342     constexpr MInt &operator-=(MInt rhs) {
    343         x = norm(x - rhs.x);
    344         return *this;
    345     }
    346     constexpr MInt &operator/=(MInt rhs) {
    347         return *this *= rhs.inv();
    348     }
    349     friend constexpr MInt operator*(MInt lhs, MInt rhs) {
    350         MInt res = lhs;
    351         res *= rhs;
    352         return res;
    353     }
    354     friend constexpr MInt operator+(MInt lhs, MInt rhs) {
    355         MInt res = lhs;
    356         res += rhs;
    357         return res;
    358     }
    359     friend constexpr MInt operator-(MInt lhs, MInt rhs) {
    360         MInt res = lhs;
    361         res -= rhs;
    362         return res;
    363     }
    364     friend constexpr MInt operator/(MInt lhs, MInt rhs) {
    365         MInt res = lhs;
    366         res /= rhs;
    367         return res;
    368     }
    369     friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
    370         i64 v;
    371         is >> v;
    372         a = MInt(v);
    373         return is;
    374     }
    375     friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
    376         return os << a.val();
    377     }
    378     friend constexpr bool operator==(MInt lhs, MInt rhs) {
    379         return lhs.val() == rhs.val();
    380     }
    381     friend constexpr bool operator!=(MInt lhs, MInt rhs) {
    382         return lhs.val() != rhs.val();
    383     }
    384 };
    385  
    386 constexpr int MOD = 1e9 + 7;
    387 using Z = MInt<MOD>;
    388  
    389 namespace comb {
    390     int n = 0;
    391     std::vector<Z> _fac = {1};
    392     std::vector<Z> _invfac = {1};
    393     std::vector<Z> _inv = {0};
    394     
    395     void init(int m) {
    396         if (m <= n) return;
    397         _fac.resize(m + 1);
    398         _invfac.resize(m + 1);
    399         _inv.resize(m + 1);
    400         
    401         for (int i = n + 1; i <= m; i++) {
    402             _fac[i] = _fac[i - 1] * i;
    403         }
    404         _invfac[m] = _fac[m].inv();
    405         for (int i = m; i > n; i--) {
    406             _invfac[i - 1] = _invfac[i] * i;
    407             _inv[i] = _invfac[i] * _fac[i - 1];
    408         }
    409         n = m;
    410     }
    411     
    412     Z fac(int m) {
    413         if (m > n) init(2 * m);
    414         return _fac[m];
    415     }
    416     Z invfac(int m) {
    417         if (m > n) init(2 * m);
    418         return _invfac[m];
    419     }
    420     Z inv(int m) {
    421         if (m > n) init(2 * m);
    422         return _inv[m];
    423     }
    424     Z binom(int m, int k) {
    425         if (m < k || k < 0) return 0;
    426         return fac(m) * invfac(k) * invfac(m - k);
    427     }
    428 } // namespace comb
    429  
    430 void solve() {
    431     int n, m1, m2;
    432     std::cin >> n >> m1 >> m2;
    433     std::vector<int> p(m1), s(m2);
    434     for (int i = 0; i < m1; i++) {
    435         std::cin >> p[i];
    436     }
    437     for (int i = 0; i < m2; i++) {
    438         std::cin >> s[i];
    439     }
    440     if (p[0] != 1 || s[0] != p[m1 - 1] || s[m2 - 1] != n) {
    441         std::cout << "0\n";
    442         return;
    443     }
    444     Z res = comb::binom(n - 1, s[0] - 1);
    445     for (int i = m1 - 2; i > -1; i--) {
    446         res *= comb::binom(p[i + 1] - 2, p[i + 1] - p[i] - 1) * comb::fac(p[i + 1] - p[i] - 1);
    447     }
    448     for (int i = 1; i < m2; i++) {
    449         res *= comb::binom(n - s[i - 1] - 1, s[i] - s[i - 1] - 1) * comb::fac(s[i] - s[i - 1] - 1);
    450     }
    451     std::cout << res << "\n";
    452 }
    453  
    454 signed main() {
    455     std::ios::sync_with_stdio(false);
    456     std::cin.tie(nullptr);
    457  
    458     #ifndef ONLINE_JUDGE
    459         freopen("/home/q1n/coding/input.txt", "r", stdin);
    460         freopen("/home/q1n/coding/output.txt", "w", stdout);
    461     #else
    462         // online submission
    463     #endif
    464  
    465     int t = 1;
    466     std::cin >> t;
    467  
    468     while (t--) {
    469         solve();
    470     }
    471 }
    472 ```
    473 
    474 author: [dope](/profile/dope "Master dope"), [yunetive29](/profile/yunetive29 "Candidate Master yunetive29"), developer: [dope](/profile/dope "Master dope"), [yunetive29](/profile/yunetive29 "Candidate Master yunetive29")
    475 
    476 [1946F - Nobody is needed](/contest/1946/problem/F "Codeforces Round 936 (Div. 2)")
    477 
    478 **Editorial**
    479 
    480 Tutorial is loading...
    481 
    482 **Solution**
    483 
    484 ```
    485 #include <bits/stdc++.h>
    486 
    487 using i64 = long long;
    488 
    489 template<class Info>
    490 struct Fenwick {
    491     std::vector<Info> t;
    492     int n;
    493     
    494     Fenwick(int n = 0) : n(n) {
    495         t.resize(n);
    496     }
    497     
    498     void add(int x, const Info &v) {
    499         for (int i = x + 1; i <= n; i += i & -i) {
    500             t[i - 1] = t[i - 1] + v;
    501         }
    502     }
    503     
    504     Info sum(int x) {
    505         x++;
    506         Info res = Info();
    507         for (int i = x; i > 0; i -= i & -i) {
    508             res = res + t[i - 1];
    509         }
    510         return res;
    511     }
    512     
    513     Info rangeSum(int l, int r) {
    514         Info res = sum(r) - sum(l - 1);
    515         return res;
    516     }
    517 };
    518 
    519 void solve() {
    520     int n, q;
    521     std::cin >> n >> q;
    522     std::vector<int> a(n), pos(n + 1);
    523     for (int i = 0; i < n; i++) {
    524         std::cin >> a[i];
    525     }
    526     std::reverse(a.begin(), a.end());
    527     for (int i = 0; i < n; i++) {
    528         pos[a[i]] = i;
    529     }
    530     constexpr int K = 19;
    531     std::vector<i64> res(q);
    532     std::vector<std::vector<std::pair<int, int>>> qry(n);
    533     for (int i = 0; i < q; i++) {
    534         int l, r;
    535         std::cin >> l >> r;
    536         l--, r--;
    537         std::swap(l, r);
    538         l = n - l - 1;
    539         r = n - r - 1;
    540         qry[r].emplace_back(l, i);
    541     }
    542     std::vector<i64> dp(n + 1);
    543     Fenwick<i64> f(n);
    544     for (int r = 0; r < n; r++) {
    545         int x = a[r];
    546         dp[x] = 1;
    547         // n * log(n) * log(n)
    548         for (int y = x; y <= n; y += x) {
    549             if (pos[y] > pos[x]) {
    550                 continue;
    551             }
    552             for (int z = 2 * y; z <= n; z += y) {
    553                 if (pos[z] > pos[y]) {
    554                     continue;
    555                 }
    556                 dp[z] += dp[y];
    557             }
    558         }
    559         // n * log(n) * log(n)
    560         for (int y = x; y <= n; y += x) {
    561             f.add(pos[y], dp[y]);
    562             dp[y] = 0;
    563         }
    564         // q * log(n)
    565         for (auto [l, i] : qry[r]) {
    566             res[i] += f.rangeSum(l, r);
    567         }
    568     }
    569     for (int i = 0; i < q; i++) {
    570         std::cout << res[i] << " \n"[i == q - 1];
    571     }
    572 }
    573 
    574 signed main() {
    575     std::ios::sync_with_stdio(false);
    576     std::cin.tie(nullptr);
    577 
    578     int t = 1;
    579     std::cin >> t;
    580 
    581     while (t--) {
    582         solve();
    583     }
    584 }
    585 ```