codeforces-scrape

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

2000.md (10394B)


      1 Source: https://codeforces.com/blog/entry/132689
      2 
      3 [2000A - Primary Task](/contest/2000/problem/A "Codeforces Round 966 (Div. 3)")
      4 
      5 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "International Master ibraevdmitriy")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     a = int(input())
     16     if 102 <= a <= 109 or 1010 <= a <= 1099:
     17         print("YES")
     18     else:
     19         print("NO")
     20 ```
     21 
     22 [2000B - Seating in a Bus](/contest/2000/problem/B "Codeforces Round 966 (Div. 3)")
     23 
     24 Idea: [myav](/profile/myav "Pupil myav")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution**
     31 
     32 ```
     33 #include <bits/stdc++.h>
     34 using namespace std;
     35 void solve(){
     36     int n;
     37     cin >> n;
     38     vector<int>a(n);
     39     for(auto &i : a) cin >> i;
     40     int left = a[0], right = a[0];
     41     for(int i = 1; i < n; i++){
     42         if(a[i] + 1 == left) left = a[i];
     43         else if(a[i] - 1 == right) right = a[i];
     44         else {
     45             cout << "NO\n";
     46             return;
     47         }
     48     }
     49     cout << "YES\n";
     50 }
     51  
     52 int main(){
     53     int t;
     54     cin >> t;
     55     while (t--) {
     56         solve();
     57     }
     58     return 0;
     59 }
     60 ```
     61 
     62 [2000C - Numeric String Template](/contest/2000/problem/C "Codeforces Round 966 (Div. 3)")
     63 
     64 Idea: [myav](/profile/myav "Pupil myav")
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution**
     71 
     72 ```
     73 def solve():
     74     n = int(input())
     75     a = list(map(int, input().split()))
     76     m = int(input())
     77     for _ in range(m):
     78         m_1 = {}
     79         m_2 = {}
     80         s = input().strip()
     81         if len(s) != n:
     82             print("NO")
     83             continue
     84  
     85         ok = True
     86         for j in range(n):
     87             if s[j] not in m_1 and a[j] not in m_2:
     88                 m_1[s[j]] = a[j]
     89                 m_2[a[j]] = s[j]
     90             elif (s[j] in m_1 and m_1[s[j]] != a[j]) or (a[j] in m_2 and m_2[a[j]] != s[j]):
     91                 ok = False
     92                 break
     93         print("YES" if ok else "NO")
     94  
     95 t = int(input())
     96 for _ in range(t):
     97     solve()
     98 ```
     99 
    100 [2000D - Right Left Wrong](/contest/2000/problem/D "Codeforces Round 966 (Div. 3)")
    101 
    102 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
    103 
    104 **Tutorial**
    105 
    106 Tutorial is loading...
    107 
    108 **Solution**
    109 
    110 ```
    111 def solve():
    112     n = int(input())
    113     a = [0]
    114     for x in input().split():
    115         x = int(x)
    116         a.append(a[-1] + x)
    117     s = input()
    118     ans = 0
    119     l = 0
    120     r = n - 1
    121     while r > l:
    122         while l < n and s[l] == 'R':
    123             l += 1
    124         while r >= 0 and s[r] == 'L':
    125             r -= 1
    126         if l < r:
    127             ans += a[r + 1] - a[l]
    128             l += 1
    129             r -= 1
    130     print(ans)
    131  
    132 t = int(input())
    133 for _ in range(t):
    134     solve()
    135 ```
    136 
    137 [2000E - Photoshoot for Gorillas](/contest/2000/problem/E "Codeforces Round 966 (Div. 3)")
    138 
    139 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
    140 
    141 **Tutorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Solution**
    146 
    147 ```
    148 #include <bits/stdc++.h>
    149  
    150 #define int long long
    151  
    152 using namespace std;
    153  
    154 #define MAXW 200200
    155 #define MAXNM 200200
    156  
    157 int n, m, k, w, p;
    158 int arr[MAXW], prr[MAXNM];
    159  
    160 static inline int calcc(int i, int j) {
    161     int upr = min(i, n - k);
    162     int leftr = min(j, m - k);
    163     int upl = max(-1LL, i - k);
    164     int leftl = max(-1LL, j - k);
    165     return (upr - upl) * (leftr - leftl);
    166 }
    167  
    168 void build() {
    169     sort(arr, arr + w);
    170     reverse(arr, arr + w);
    171     p = 0;
    172     for (int i = 0; i < n; ++i)
    173         for (int j = 0; j < m; ++j)
    174             prr[p++] = calcc(i, j);
    175     sort(prr, prr + p);
    176     reverse(prr, prr + p);
    177 }
    178  
    179 int solve() {
    180     int sum = 0;
    181     for (int i = 0; i < w; ++i)
    182         sum += prr[i] * arr[i];
    183     return sum;
    184 }
    185  
    186 signed main() {
    187     int t; cin >> t;
    188     while (t--) {
    189         cin >> n >> m >> k >> w;
    190         for (int i = 0; i < w; ++i)
    191             cin >> arr[i];
    192         build();
    193         cout << solve() << endl;
    194     }
    195 }
    196 ```
    197 
    198 [2000F - Color Rows and Columns](/contest/2000/problem/F "Codeforces Round 966 (Div. 3)")
    199 
    200 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "International Master ibraevdmitriy")
    201 
    202 **Tutorial**
    203 
    204 Tutorial is loading...
    205 
    206 **Solution**
    207 
    208 ```
    209 #include <iostream>
    210 #include <algorithm>
    211 #include <vector>
    212  
    213 using namespace std;
    214  
    215 void solve() {
    216     int n, k;
    217     cin >> n >> k;
    218     vector<int> a(n), b(n);
    219     for (int i = 0; i < n; ++i) {
    220         cin >> a[i] >> b[i];
    221     }
    222     vector<vector<int>> dp(n + 1, vector<int>(k + 1, 1e9));
    223     dp[0][0] = 0;
    224     for (int i = 0; i < n; ++i) {
    225         int x = a[i], y = b[i];
    226         int xy = x + y;
    227         int cost = 0;
    228         for (int j = 0; j <= xy; ++j) {
    229             for (int j1 = 0; j1 + j <= k; ++j1) {
    230                 dp[i + 1][j1 + j] = min(dp[i + 1][j1 + j], dp[i][j1] + cost);
    231             }
    232             if (j < xy) {
    233                 if (x >= y) {
    234                     x--, cost += y;
    235                 } else {
    236                     y--, cost += x;
    237                 }
    238             }
    239         }
    240     }
    241     cout << (dp[n][k] == 1e9 ? -1 : dp[n][k]) << '\n';
    242 }
    243  
    244 int main() {
    245     int t;
    246     cin >> t;
    247     for (int i = 0; i < t; ++i) {
    248         solve();
    249     }
    250     return 0;
    251 }
    252 ```
    253 
    254 [2000G - Call During the Journey](/contest/2000/problem/G "Codeforces Round 966 (Div. 3)")
    255 
    256 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "International Master ibraevdmitriy")
    257 
    258 **Tutorial**
    259 
    260 Tutorial is loading...
    261 
    262 **Solution**
    263 
    264 ```
    265 #include <iostream>
    266 #include <vector>
    267 #include <set>
    268  
    269 using namespace std;
    270  
    271 void solve() {
    272     int n, m;
    273     cin >> n >> m;
    274     int t0, t1, t2;
    275     cin >> t0 >> t1 >> t2;
    276     vector<vector<vector<int>>> g(n);
    277     for (int i = 0; i < m; ++i) {
    278         int u, v, l1, l2;
    279         cin >> u >> v >> l1 >> l2;
    280         u--, v--;
    281         g[u].push_back({v, l1, l2});
    282         g[v].push_back({u, l1, l2});
    283     }
    284     set<pair<int, int>> prq;
    285     prq.insert({t0, n - 1});
    286     for (int i = 0; i + 1 < n; ++i) {
    287         prq.insert({-1e9, i});
    288     }
    289     vector<int> dist(n, -1e9);
    290     dist[n - 1] = t0;
    291     while (!prq.empty()) {
    292         auto p = *prq.rbegin();
    293         prq.erase(p);
    294         int d = p.first, u = p.second;
    295         for (auto e: g[u]) {
    296             int v = e[0], l1 = e[1], l2 = e[2];
    297             int d1 = (d - l1 >= t2 || d <= t1) ? d - l1 : d - l2;
    298             if(d1 == d - l2) d1 = max(d1, t1 - l1);
    299             if (dist[v] < d1) {
    300                 prq.erase({dist[v], v});
    301                 dist[v] = d1;
    302                 prq.insert({d1, v});
    303             }
    304         }
    305     }
    306     cout << (dist[0] >= 0 ? dist[0] : -1) << '\n';
    307 }
    308  
    309 int main() {
    310     int t;
    311     cin >> t;
    312     for (int i = 0; i < t; ++i) {
    313         solve();
    314     }
    315     return 0;
    316 }
    317 ```
    318 
    319 [2000H - Ksyusha and the Loaded Set](/contest/2000/problem/H "Codeforces Round 966 (Div. 3)")
    320 
    321 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "International Master ibraevdmitriy")
    322 
    323 **Tutorial**
    324 
    325 Tutorial is loading...
    326 
    327 **Solution**
    328 
    329 ```
    330 #pragma GCC optimize("O3,unroll-loops")
    331  
    332 #include <bits/stdc++.h>
    333  
    334 #define endl '\n'
    335  
    336 using namespace std;
    337  
    338 typedef pair<int, int> ipair;
    339  
    340 #define INF 1'000'000'009
    341 #define MAXN 200200
    342 #define MAXMEM 5'000'000
    343 #define MAXLEN 2'000'100
    344  
    345 #define X first
    346 #define Y second
    347  
    348 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    349  
    350 struct node {
    351     node *lv = nullptr, *rv = nullptr;
    352     ipair key;
    353     int prior;
    354     int minl = INF;
    355     
    356     node(const ipair& key) : key(key), prior(rng()), minl(key.Y) {}
    357 };
    358  
    359 static inline int minl(node *v) {
    360     return (v == nullptr ? INF : v->minl);
    361 }
    362  
    363 static inline void upd(node *v) {
    364     v->minl = min(v->key.Y, min(minl(v->lv), minl(v->rv)));
    365 }
    366  
    367 node *merge(node *s1, node *s2) {
    368     if (s1 == nullptr) return s2;
    369     if (s2 == nullptr) return s1;
    370     if (s1->prior > s2->prior) {
    371         s1->rv = merge(s1->rv, s2);
    372         upd(s1);
    373         return s1;
    374     } else {
    375         s2->lv = merge(s1, s2->lv);
    376         upd(s2);
    377         return s2;
    378     }
    379 }
    380  
    381 pair<node*, node*> split(node* &v, ipair x) {
    382     if (v == nullptr) {
    383         return {nullptr, nullptr};
    384     }
    385     if (v->key < x) {
    386         auto [s1, s2] = split(v->rv, x);
    387         v->rv = s1;
    388         upd(v);
    389         return {v, s2};
    390     } else {
    391         auto [s1, s2] = split(v->lv, x);
    392         v->lv = s2;
    393         upd(v);
    394         return {s1, v};
    395     }
    396 }
    397  
    398 int n, m;
    399 int arr[MAXN];
    400 node *mem = (node*)calloc(MAXMEM, sizeof(*mem));
    401 node *mpos = mem;
    402 node *root;
    403 set<int> M;
    404  
    405 // [l..r)
    406 void add_seg(int l, int r) {
    407     if (l >= r) return;
    408     ipair p {r - l, l};
    409     auto [s1, s2] = split(root, p);
    410     node *v = mpos++;
    411     *v = node(p);
    412     root = merge(merge(s1, v), s2);
    413 }
    414  
    415 void rem_dek(node* &v, const ipair& x) {
    416     if (v == nullptr) return;
    417     if (v->key == x) {
    418         v = merge(v->lv, v->rv);
    419         if (v) upd(v);
    420         return;
    421     }
    422     if (v->key < x) rem_dek(v->rv, x);
    423     else rem_dek(v->lv, x);
    424     upd(v);
    425 }
    426  
    427 // [l..r)
    428 void rem_seg(int l, int r) {
    429     if (l >= r) return;
    430     ipair p {r - l, l};
    431     rem_dek(root, p);
    432 }
    433  
    434 void add_val(int x) {
    435     auto it = M.lower_bound(x);
    436     int clsl = (it == M.begin() ? 0 : *prev(it));
    437     int clsr = (it == M.end() ? INF : *it);
    438     rem_seg(clsl + 1, clsr);
    439     add_seg(clsl + 1, x);
    440     if (clsr != INF) add_seg(x + 1, clsr);
    441     M.insert(x);
    442 }
    443  
    444 void rem_val(int x) {
    445     auto it = M.lower_bound(x);
    446     int clsl = (it == M.begin() ? 0 : *prev(it));
    447     int clsr = (next(it) == M.end() ? INF : *next(it));
    448     rem_seg(clsl + 1, x);
    449     rem_seg(x + 1, clsr);
    450     if (clsr != INF) add_seg(clsl + 1, clsr);
    451     M.erase(x);
    452 }
    453  
    454 int query(int k) {
    455     if (M.empty()) return 1;
    456     auto [s1, s2] = split(root, make_pair(k, -1));
    457     fprintf(stderr, "AMOGUS: %p, %p\n", s1, s2);
    458     int ans = min(*M.rbegin() + 1, minl(s2));
    459     root = merge(s1, s2);
    460     return ans;
    461 }
    462  
    463 void init() {
    464     root = nullptr;
    465     mpos = mem;
    466     M = {arr, arr + n};
    467     add_seg(1, *M.begin());
    468     for (auto it = M.begin(); next(it) != M.end(); ++it)
    469         add_seg(*it + 1, *next(it));
    470 }
    471  
    472 signed main() {
    473     int t; cin >> t;
    474     while (t--) {
    475         cin >> n;
    476         for (int i = 0; i < n; ++i)
    477             cin >> arr[i];
    478         init();
    479         cin >> m;
    480         for (int j = 0; j < m; ++j) {
    481             char tp; cin >> tp;
    482             int x, k;
    483             switch (tp) {
    484             case '+':
    485                 cin >> x;
    486                 add_val(x);
    487                 break;
    488             case '-':
    489                 cin >> x;
    490                 rem_val(x);
    491                 break;
    492             case '?':
    493                 cin >> k;
    494                 cout << query(k) << " ";
    495                 break;
    496             }
    497         }
    498         cout << endl;
    499     }
    500 }
    501 ```