codeforces-scrape

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

2244.md (7675B)


      1 Source: https://codeforces.com/blog/entry/155197
      2 
      3 [2244A - Iskander and Drawings](/contest/2244/problem/A "Codeforces Round 1109 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using ll = long long;
     15 using namespace std;
     16 
     17 void I_love_feblokas();
     18 
     19 int32_t main() {
     20     int32_t tc = 1;
     21     cin >> tc;
     22     while (tc-->0) {
     23         I_love_feblokas();
     24     }
     25     return 0;
     26 }
     27 
     28 void I_love_feblokas() {
     29     int32_t ans = 0, cnt = 0;
     30     int n;
     31     cin >> n;
     32     string s;
     33     cin >> s;
     34     for (auto &c : s) {
     35         if (c == '*') {
     36             cnt = 0;
     37         } else {
     38             cnt++;
     39         }
     40         ans = max(ans, (cnt + 1) / 2);
     41     }
     42     cout << ans << '\n';
     43     return;
     44 }
     45 ```
     46 
     47 [2244B - Nikita and Books](/contest/2244/problem/B "Codeforces Round 1109 (Div. 3)")
     48 
     49 **Tutorial**
     50 
     51 Tutorial is loading...
     52 
     53 **Solution**
     54 
     55 ```
     56 #include <bits/stdc++.h>
     57 
     58 using ll = long long;
     59 using namespace std;
     60 
     61 void I_love_feblokas();
     62 
     63 int32_t main() {
     64     int32_t tc = 1;
     65     cin >> tc;
     66     while (tc-- > 0) {
     67         I_love_feblokas();
     68     }
     69     return 0;
     70 }
     71 
     72 void I_love_feblokas() {
     73     int n;
     74     cin >> n;
     75     vector<ll> a(n);
     76     for (auto &x : a) cin >> x;
     77     ll cur = 0;
     78     bool ok = true;
     79     for (ll i = 0; i < n; ++i) {
     80         cur += a[i];
     81         ll need = (i + 1) * (i + 2) / 2;
     82         if (cur < need) {
     83             ok = false;
     84         }
     85     }
     86     if (ok) {
     87         cout << "YES\n";
     88     } else {
     89         cout << "NO\n";
     90     }
     91 }
     92 ```
     93 
     94 [2244C - Stepan and Permutation](/contest/2244/problem/C "Codeforces Round 1109 (Div. 3)")
     95 
     96 **Tutorial**
     97 
     98 Tutorial is loading...
     99 
    100 **Solution**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 
    105 using ll = long long;
    106 using namespace std;
    107 
    108 void I_love_feblokas();
    109 
    110 int32_t main() {
    111     int32_t tc = 1;
    112     cin >> tc;
    113     while (tc-- > 0) {
    114         I_love_feblokas();
    115     }
    116     return 0;
    117 }
    118 
    119 void I_love_feblokas() {
    120     int n, x, y;
    121     cin >> n >> x >> y;
    122     vector<int> p(n);
    123     for (auto &val : p) cin >> val;
    124     
    125     int g = gcd(x, y);
    126     bool ok = true;
    127     
    128     for (int i = 0; i < n; ++i) {
    129         if ((p[i] % g) != ((i + 1) % g)) {
    130             ok = false;
    131             break;
    132         }
    133     }
    134     
    135     if (ok) {
    136         cout << "YES\n";
    137     } else {
    138         cout << "NO\n";
    139     }
    140 }
    141 ```
    142 
    143 [2244D - Yaroslav and Productivity](/contest/2244/problem/D "Codeforces Round 1109 (Div. 3)")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution**
    150 
    151 ```
    152 #include <bits/stdc++.h>
    153 
    154 using ll = long long;
    155 using namespace std;
    156 
    157 void I_love_feblokas();
    158 
    159 int32_t main() {
    160     int32_t tc = 1;
    161     cin >> tc;
    162     while (tc-->0) {
    163         I_love_feblokas();
    164     }
    165     return 0;
    166 }
    167 
    168 void I_love_feblokas() {
    169     int n, m;
    170     ll ans = 0;
    171     cin >> n >> m;
    172     vector<ll> a(n), b(m);
    173     for (auto &x : a) cin >> x;
    174     for (auto &x : b) cin >> x;
    175     b.push_back(0);
    176     sort(b.begin(), b.end());
    177     vector<ll> pref(n + 1);
    178     for (ll i = 0; i < n; ++i) {
    179         pref[i + 1] = pref[i] + a[i];
    180     }
    181     for (ll i = 1; i < b.size(); ++i) {
    182         ans += abs(pref[b[i]] - pref[b[i - 1]]);
    183     }
    184     ans += pref[n] - pref[b.back()];
    185     cout << ans << '\n';
    186     return;
    187 }
    188 ```
    189 
    190 [2244E - Masha and the Garland](/contest/2244/problem/E "Codeforces Round 1109 (Div. 3)")
    191 
    192 **Tutorial**
    193 
    194 Tutorial is loading...
    195 
    196 **Solution**
    197 
    198 ```
    199 #include <bits/stdc++.h>
    200 
    201 using namespace std;
    202 
    203 void solve() {
    204     int n, q;
    205     cin >> n >> q;
    206     string s;
    207     cin >> s;
    208     vector<int> pref(n, 0);
    209     for (int i = 0; i < n &mdash; 1; ++i) {
    210         pref[i + 1] = pref[i] + (s[i] == s[i + 1] ? 1 : 0);
    211     }
    212     for (int i = 0; i < q; ++i) {
    213         int l, r, k;
    214         cin >> l >> r >> k;
    215         if (l == r) {
    216             cout << "YES\n";
    217             continue;
    218         }
    219         int c = pref[r &mdash; 1] &mdash; pref[l &mdash; 1];
    220         int needed = (c + 1) / 2;
    221         if (needed <= k) cout << "YES\n";
    222         else cout << "NO\n";
    223     }
    224 }
    225 
    226 int main() {
    227     int t;
    228     cin >> t;
    229     while (t--) solve();
    230     return 0;
    231 }
    232 ```
    233 
    234 [2244F - Anya Loves Trees!](/contest/2244/problem/F "Codeforces Round 1109 (Div. 3)")
    235 
    236 **Tutorial**
    237 
    238 Tutorial is loading...
    239 
    240 **Solution**
    241 
    242 ```
    243 #include <bits/stdc++.h>
    244 
    245 using ll = long long;
    246 using namespace std;
    247 
    248 vector<vector<int>> g;
    249 vector<int> leaf;
    250 bool ok;
    251 
    252 void I_love_feblokas();
    253 pair<int, int> dfs(int u, int p);
    254 
    255 int32_t main() {
    256     int32_t tc = 1;
    257     cin >> tc;
    258     while (tc-- > 0) {
    259         I_love_feblokas();
    260     }
    261     return 0;
    262 }
    263 
    264 pair<int, int> dfs(int u, int p) {
    265     if (!ok) return {0, 0};
    266     if (leaf[u] != 0) {
    267         for (int v : g[u]) {
    268             if (v != p) {
    269                 ok = false;
    270                 return {0, 0};
    271             }
    272         }
    273         return {leaf[u], leaf[u]};
    274     }
    275     vector<pair<int, int>> segs;
    276     for (int v : g[u]) {
    277         if (v != p) {
    278             segs.push_back(dfs(v, u));
    279             if (!ok) return {0, 0};
    280         }
    281     }
    282     if (segs.empty()) {
    283         ok = false;
    284         return {0, 0};
    285     }
    286     vector<pair<int, int>> sorted_segs = segs;
    287     sort(sorted_segs.begin(), sorted_segs.end());
    288     for (size_t i = 0; i < sorted_segs.size() &mdash; 1; ++i) {
    289         if (sorted_segs[i].second + 1 != sorted_segs[i + 1].first) {
    290             ok = false;
    291             return {0, 0};
    292         }
    293     }
    294     int start_pos = -1;
    295     for (size_t i = 0; i < segs.size(); ++i) {
    296         if (segs[i] == sorted_segs[0]) {
    297             start_pos = i;
    298             break;
    299         }
    300     }
    301     if (start_pos == -1) {
    302         ok = false;
    303         return {0, 0};
    304     }
    305     for (size_t i = 0; i < segs.size(); ++i) {
    306         if (segs[(start_pos + i) % segs.size()] != sorted_segs[i]) {
    307             ok = false;
    308             return {0, 0};
    309         }
    310     }
    311     return {sorted_segs[0].first, sorted_segs.back().second};
    312 }
    313 
    314 void I_love_feblokas() {
    315     int n;
    316     cin >> n;
    317     g.assign(n + 1, vector<int>());
    318     leaf.assign(n + 1, 0);
    319     ok = true;
    320     for (int i = 2; i <= n; ++i) {
    321         int p;
    322         cin >> p;
    323         g[p].push_back(i);
    324         g[i].push_back(p);
    325     }
    326     int k = 0;
    327     for (int i = 1; i <= n; ++i) {
    328         cin >> leaf[i];
    329         k = max(k, leaf[i]);
    330     }
    331     if (n == 1) {
    332         cout << "YES\n";
    333         return;
    334     }
    335     pair<int, int> res = dfs(1, -1);
    336     if (ok && res.first == 1 && res.second == k) {
    337         cout << "YES\n";
    338     } else {
    339         cout << "NO\n";
    340     }
    341 }
    342 ```
    343 
    344 [2244G - Yura and Deadlines](/contest/2244/problem/G "Codeforces Round 1109 (Div. 3)")
    345 
    346 **Tutorial**
    347 
    348 Tutorial is loading...
    349 
    350 **Solution**
    351 
    352 ```
    353 #include <bits/stdc++.h>
    354 
    355 using namespace std;
    356 using ll = long long;
    357 
    358 struct Fenwick {
    359     int n;
    360     vector<ll> t;
    361     
    362     Fenwick(int n) : n(n), t(n + 1, 0ll) {}
    363     
    364     int f(int x) {
    365         return x & -x;
    366     }
    367     
    368     void upd(int pos, ll val) {
    369         for (; pos <= n; pos += f(pos)) t[pos] = max(t[pos], val);
    370     }
    371     
    372     ll get(int pos) {
    373         ll ans = 0;
    374         for (; pos > 0; pos -= f(pos)) ans = max(ans, t[pos]);
    375         return ans;
    376     }
    377 };
    378 
    379 void I_love_feblokas() {
    380     int n;
    381     cin >> n;
    382     vector<ll> a(n + 1);
    383     for (int i = 1; i <= n; ++i) {
    384         cin >> a[i];
    385     }
    386     Fenwick t(n);
    387     vector<vector<pair<int, ll>>> ev(n + 1);
    388     ll ans = 0;
    389     for (int i = 1; i <= n; ++i) {
    390         for (auto& ev : ev[i]) {
    391             t.upd(ev.first, ev.second);
    392         }
    393         int lim = i - a[i] - 1;
    394         ll mx = 0;
    395         if (lim > 0) {
    396             mx = t.get(min(n, lim));
    397         }
    398         ll dp_i = a[i] + mx;
    399         ans = max(ans, dp_i);
    400         ll act = i + a[i] + 1;
    401         if (act <= n) {
    402             ev[act].push_back({i, dp_i});
    403         }
    404     }
    405     cout << ans << "\n";
    406 }
    407 
    408 int main() {
    409     int t;
    410     cin >> t ;
    411     while (t--) {
    412         I_love_feblokas();
    413     }
    414     return 0;
    415 }
    416 ```