codeforces-scrape

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

1635.md (7920B)


      1 Source: https://codeforces.com/blog/entry/100153
      2 
      3 [1635A - Min Or Sum](/contest/1635/problem/A "Codeforces Round 772 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 using namespace std;
     14 
     15 int main () {
     16     ios::sync_with_stdio(false);
     17     cin.tie(0);
     18     int t;
     19     cin >> t;
     20     while (t--) {
     21         int n;
     22         cin >> n;
     23         int ans = 0;
     24         for (int i = 0, x; i < n; ++i) {
     25             cin >> x;
     26             ans |= x;
     27         }
     28         cout << ans << endl;
     29     }
     30 }
     31 ```
     32 
     33 [1635B - Avoid Local Maximums](/contest/1635/problem/B "Codeforces Round 772 (Div. 2)")
     34 
     35 **Tutorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution**
     40 
     41 ```
     42 #include <bits/stdc++.h>
     43 using namespace std;
     44 
     45 int main () {
     46     ios::sync_with_stdio(false);
     47     cin.tie(0);
     48     int t;
     49     cin >> t;
     50     while (t--) {
     51         int n;
     52         cin >> n;
     53         vector <int> a(n);
     54         for (int i = 0; i < n; ++i) {
     55             cin >> a[i];
     56         }
     57         int ans = 0;
     58         for (int i = 1; i + 1 < n; ++i) {
     59             if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
     60                 if (i + 2 < n) {
     61                     a[i + 1] = max(a[i], a[i + 2]);
     62                 } else {
     63                     a[i + 1] = a[i];
     64                 }
     65                 ans++;
     66             }
     67         }
     68         cout << ans << endl;
     69         for (int i = 0; i < n; ++i) {
     70             cout << a[i] << " \n"[i == n - 1];
     71         }
     72     }
     73 }
     74 ```
     75 
     76 [1635C - Differential Sorting](/contest/1635/problem/C "Codeforces Round 772 (Div. 2)")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution**
     83 
     84 ```
     85 #include <bits/stdc++.h>
     86 using namespace std;
     87 
     88 int main () {
     89     ios::sync_with_stdio(false);
     90     cin.tie(0);
     91     int t;
     92     cin >> t;
     93     while (t--) {
     94         int n;
     95         cin >> n;
     96         vector <int> a(n);
     97         for (int i = 0; i < n; ++i) {
     98             cin >> a[i];
     99         }
    100         if (a[n - 2] > a[n - 1]) {
    101             cout << -1 << endl;
    102         } else {
    103             if (a[n - 1] < 0) {
    104                 if (is_sorted(a.begin(), a.end())) {
    105                     cout << 0 << endl;
    106                 } else {
    107                     cout << -1 << endl;
    108                 }
    109             } else {
    110                 cout << n - 2 << endl;
    111                 for (int i = 1; i <= n - 2; ++i) {
    112                     cout << i << ' ' << n - 1 << ' ' << n << endl;
    113                 }
    114             }
    115         }
    116     }
    117 }
    118 ```
    119 
    120 [1635D - Infinite Set](/contest/1635/problem/D "Codeforces Round 772 (Div. 2)")
    121 
    122 **Tutorial**
    123 
    124 Tutorial is loading...
    125 
    126 **Solution**
    127 
    128 ```
    129 #include <bits/stdc++.h>
    130 using namespace std;
    131 
    132 const int mod = 1e9 + 7;
    133 
    134 int main () {
    135     ios::sync_with_stdio(false);
    136     cin.tie(0);
    137     int n, p;
    138     cin >> n >> p;
    139     vector <int> a(n);
    140     for (int i = 0; i < n; ++i) {
    141         cin >> a[i];
    142     }
    143     sort(a.begin(), a.end());
    144     set <int> useful;
    145     for (int i = 0; i < n; ++i) {
    146         int x = a[i];
    147         bool flag = false;
    148         while (x > 0) {
    149             if (useful.count(x)) {
    150                 flag = true;
    151             }
    152             if (x & 1) {
    153                 x >>= 1;
    154             } else if (x & 3) {
    155                 break;
    156             } else {
    157                 x >>= 2;
    158             }
    159         }
    160         if (!flag)
    161             useful.insert(a[i]);
    162     }
    163     vector <int> cnt(30, 0), dp(p);
    164     for (int x : useful) {
    165         cnt[__lg(x)]++;
    166     }
    167     int ans = 0;
    168     for (int i = 0; i < p; ++i) {
    169         if (i < 30) {
    170             dp[i] = cnt[i];
    171         }
    172         if (i >= 1) {
    173             dp[i] += dp[i - 1];
    174             if (dp[i] >= mod) {
    175                 dp[i] -= mod;
    176             }
    177         }
    178         if (i >= 2) {
    179             dp[i] += dp[i - 2];
    180             if (dp[i] >= mod) {
    181                 dp[i] -= mod;
    182             }
    183         }
    184         ans += dp[i];
    185         if (ans >= mod) {
    186             ans -= mod;
    187         }
    188     }
    189     cout << ans << endl;
    190 }
    191 ```
    192 
    193 [1635E - Cars](/contest/1635/problem/E "Codeforces Round 772 (Div. 2)")
    194 
    195 **Tutorial**
    196 
    197 Tutorial is loading...
    198 
    199 **Solution**
    200 
    201 ```
    202 #include <bits/stdc++.h>
    203 using namespace std;
    204 
    205 const int N = 200001;
    206 
    207 struct edge {
    208     int type, u, v;
    209 };
    210 
    211 vector <int> adj[N];
    212 int col[N], topo[N];
    213 
    214 void dfs(int v) {
    215     for (int u : adj[v]) if (col[u] == -1) {
    216         col[u] = col[v] ^ 1;
    217         dfs(u);
    218     }
    219 }
    220 
    221 bool BipartiteColoring(int n) {
    222     for (int i = 1; i <= n; ++i)
    223         col[i] = -1;
    224     for (int i = 1; i <= n; ++i) if (col[i] == -1) {
    225         col[i] = 0;
    226         dfs(i);
    227     }
    228     for (int i = 1; i <= n; ++i) for (int j : adj[i]) {
    229         if (col[i] == col[j]) {
    230             return false;
    231         }
    232     }
    233     return true;
    234 }
    235 
    236 bool TopologicalSort(int n) {
    237     vector <int> in(n + 1, 0);
    238     for (int i = 1; i <= n; ++i) for (int j : adj[i]) {
    239         in[j]++;
    240     }
    241     queue <int> q;
    242     for (int i = 1; i <= n; ++i) if (in[i] == 0) {
    243         q.push(i);
    244     }
    245     int ord = 0;
    246     while (!q.empty()) {
    247         int v = q.front(); q.pop();
    248         topo[v] = ord++;
    249         for (int u : adj[v]) {
    250             in[u]--;
    251             if (in[u] == 0) {
    252                 q.push(u);
    253             }
    254         }
    255     }
    256     return ord == n;
    257 }
    258 
    259 int main () {
    260     ios::sync_with_stdio(false);
    261     cin.tie(0);
    262     int n, m;
    263     cin >> n >> m;
    264     vector <edge> a(m);
    265     for (int i = 0; i < m; ++i) {
    266         cin >> a[i].type >> a[i].u >> a[i].v;
    267         adj[a[i].u].push_back(a[i].v);
    268         adj[a[i].v].push_back(a[i].u);
    269     }
    270     if (!BipartiteColoring(n)) {
    271         cout << "NO" << endl;
    272         return 0;
    273     }
    274     // col = 0 -> orient left, col = 1 -> orient right
    275     for (int i = 1; i <= n; ++i) {
    276         adj[i].clear();
    277     }
    278     for (edge e : a) {
    279         if (col[e.u] == 1)
    280             swap(e.u, e.v);
    281         if (e.type == 1) {
    282             adj[e.u].push_back(e.v);
    283         } else {
    284             adj[e.v].push_back(e.u);
    285         }
    286     }
    287     if (!TopologicalSort(n)) {
    288         cout << "NO" << endl;
    289         return 0;
    290     }
    291     cout << "YES" << endl;
    292     for (int i = 1; i <= n; ++i) {
    293         cout << (col[i] == 0 ? "L " : "R ") << topo[i] << endl;
    294     }
    295 }
    296 ```
    297 
    298 [1635F - Closest Pair](/contest/1635/problem/F "Codeforces Round 772 (Div. 2)")
    299 
    300 **Tutorial**
    301 
    302 Tutorial is loading...
    303 
    304 **Solution**
    305 
    306 ```
    307 #include <bits/stdc++.h>
    308 using namespace std;
    309 
    310 const int N = 300005;
    311 const long long INF = 1ll << 62;
    312 
    313 vector <int> useful_pair[N];
    314 vector <pair <int, int>> queries[N];
    315 
    316 long long bit[N];
    317 
    318 void modify(int p, long long v) {
    319     for (int i = p; i > 0; i -= i & (-i)) {
    320         bit[i] = min(bit[i], v);
    321     }
    322 }
    323 
    324 long long query(int p) {
    325     long long ans = INF;
    326     for (int i = p; i < N; i += i & (-i)) {
    327         ans = min(ans, bit[i]);
    328     }
    329     return ans;
    330 }
    331 
    332 int main () {
    333     ios::sync_with_stdio(false);
    334     cin.tie(0);
    335     int n, q;
    336     cin >> n >> q;
    337     vector <int> x(n), w(n);
    338     for (int i = 0; i < n; ++i) {
    339         cin >> x[i] >> w[i];
    340     }
    341     for (int i = 0, l, r; i < q; ++i) {
    342         cin >> l >> r, --l;
    343         queries[r].emplace_back(l, i);
    344     }
    345     stack <int> stk;
    346     for (int i = 0; i < n; ++i) {
    347         while (!stk.empty() && w[stk.top()] > w[i]) {
    348             stk.pop();
    349         }
    350         if (!stk.empty()) {
    351             int x = stk.top();
    352             useful_pair[i].push_back(x);
    353         }
    354         stk.push(i);
    355     }
    356     while (!stk.empty()) {
    357         stk.pop();
    358     }
    359     for (int i = n - 1; ~i; --i) {
    360         while (!stk.empty() && w[stk.top()] > w[i]) {
    361             stk.pop();
    362         }
    363         if (!stk.empty()) {
    364             int x = stk.top();
    365             useful_pair[x].push_back(i);
    366         }
    367         stk.push(i);
    368     }
    369     fill(bit, bit + N, INF);
    370     vector <long long> ans(q);
    371     for (int r = 1; r <= n; ++r) {
    372         for (int l : useful_pair[r - 1]) {
    373             long long val = 1ll * (x[r - 1] - x[l]) * (w[l] + w[r - 1]);
    374             modify(l + 1, val);
    375         }
    376         for (auto [l, id] : queries[r]) {
    377             ans[id] = query(l + 1);
    378         }
    379     }
    380     for (int i = 0; i < q; ++i) {
    381         cout << ans[i] << endl;
    382     }
    383 }
    384 ```