Codeforces Round #892 (Div. 2) Editorial
Difference between ru2 and ru3, changed 1 character(s)
Надеемся, что вам понравились наши задачи!↵

[problem:1858A]↵

<spoiler summary="Tutorial">↵
[tutorial:1858A]↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
t = int(input())↵
for i in range(t):↵
    a, b, c = map(int, input().split())↵
    if c % 2 == 0:↵
        if a > b:↵
            print("First")↵
        else:↵
            print("Second")↵
    else:↵
        if b > a:↵
            print("Second")↵
        else:↵
            print("First")↵
~~~~~↵
</spoiler>↵

[problem:1858B]↵

<spoiler summary="Tutorial">↵
[tutorial:1858B]↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

int solve(int d, vector<int> x)↵
{↵
    int ans = 0;↵
    for (int i = 1; i < x.size(); i++)↵
    {↵
        ans += (x[i] - x[i - 1] - 1) / d;↵
    }↵
    ans += int(x.size()) - 2;↵
    return ans;↵
}↵

void solve()↵
{↵
    #define tests↵

    int n, m, d;↵
    cin >> n >> m >> d;↵
    vector<int> r(m);↵
    for (int i = 0; i < m; i++) cin >> r[i];↵
    r.push_back(1 - d);↵
    r.push_back(n + 1);↵

    sort(r.begin(), r.end());↵

    int ans = 2e9;↵
    vector<int> res;↵
    for (int i = 1; i <= m; i++)↵
    {↵
        int A = r[i] - r[i - 1] - 1;↵
        int B = r[i + 1] - r[i] - 1;↵
        int C = r[i + 1] - r[i - 1] - 1;↵
        int D = C / d - (A / d + B / d);↵
        if (D < ans)↵
        {↵
            ans = D;↵
            res.clear();↵
        }↵
        if (D == ans)↵
        {↵
            res.push_back(r[i]);↵
        }↵
    }↵
    cout << ans + solve(d, r) - 1 << ' ' << res.size() << endl;↵
}↵

int main()↵
{↵
    int t = 1;↵
    #ifdef tests↵
    cin >> t;↵
    #endif↵
    while (t--)↵
    {↵
        solve();↵
    }↵
}↵
~~~~~↵
</spoiler>↵

[problem:1858C]↵

<spoiler summary="Tutorial">↵
[tutorial:1858C]↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
#include<iostream>↵
#include<vector>↵

using namespace std;↵

int main() {↵
    int t;↵
    cin >> t;↵
    while (t--) {↵
        int n;↵
        cin >> n;↵
        vector<int> a(n);↵
        int cur = 0;↵
        for (int i = 1; i <= n; i += 2) {↵
            for (int j = i; j <= n; j *= 2) {↵
                a[cur++] = j;↵
            }↵
        }↵
        for (int i = 0; i<n; ++i) {↵
            cout << a[i] << " ";↵
        }↵
        cout << '\n';↵
    }↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

[problem:1858D]↵

<spoiler summary="Tutorial">↵
[tutorial:1858D]↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵

#define int long long↵

using namespace std;↵
using ll = long long;↵

void solve();↵

template<typename ...Args>↵
void println(Args... args) {↵
    apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));↵
    cout << '\n';↵
}↵

int32_t main() {↵
    cin.tie(nullptr);↵
    ios_base::sync_with_stdio(false);↵
    int t = 1;↵
    cin >> t;↵
    for (int tc = 0; tc < t; ++tc) {↵
        solve();↵
    }↵
    return 0;↵
}↵

void solve() {↵
    int n, k;↵
    cin >> n >> k;↵
    string s;↵
    cin >> s;↵
    vector<int> max0by1(n + 1, -1e9);↵
    vector<vector<int>> max0pref(n + 1, vector<int>(n + 1));↵
    vector<vector<int>> max0suf(n + 1, vector<int>(n + 1));↵
    for (int l = 0; l < n; ++l) {↵
        int cnt1 = 0;↵
        for (int r = l + 1; r <= n; ++r) {↵
            cnt1 += s[r - 1] == '1';↵
            max0pref[r][cnt1] = max(max0pref[r][cnt1], r - l);↵
            max0suf[l][cnt1] = max(max0suf[l][cnt1], r - l);↵
        }↵
    }↵
    for (int r = 0; r <= n; ++r) {↵
        for (int cnt = 0; cnt <= n; ++cnt) {↵
            if (r) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r - 1][cnt]);↵
            if (cnt) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r][cnt - 1]);↵
        }↵
    }↵
    for (int l = n; l >= 0; --l) {↵
        for (int cnt = 0; cnt <= n; ++cnt) {↵
            if (l + 1 <= n) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l + 1][cnt]);↵
            if (cnt) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l][cnt - 1]);↵
        }↵
    }↵
    vector<int> ans(n + 1, -1e9);↵
    for (int l = 0; l < n; ++l) {↵
        int cnt0 = 0;↵
        for (int r = l; r <= n; ++r) {↵
            if (r > l) cnt0 += s[r - 1] == '0';↵
            if (cnt0 > k) break;↵
            max0by1[r - l] = max(max0by1[r - l], max0pref[l][k - cnt0]);↵
            max0by1[r - l] = max(max0by1[r - l], max0suf[r][k - cnt0]);↵
        }↵
    }↵
    for (int i = 0; i <= n; ++i) {↵
        for (int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);↵
    }↵
    for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';↵
    cout << '\n';↵
}↵
~~~~~↵
</spoiler>↵

[problem:1858E2]↵

<spoiler summary="Tutorial">↵
[tutorial:1858E2]↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <numeric>↵
#include <set>↵

using namespace std;↵

const int maxn = 1e6 + 1;↵

int f[maxn];↵

int get(int i) {↵
    int ans = 0;↵
    while (i >= 0) {↵
        ans += f[i];↵
        i = (i & (i + 1)) - 1;↵
    }↵
    return ans;↵
}↵

void upd(int i, int x) {↵
    while (i < maxn) {↵
        f[i] += x;↵
        i = i | (i + 1);↵
    }↵
}↵

int a[maxn];↵
int rev[maxn];↵
set<int> ids[maxn];↵

int32_t main() {↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(0);↵
    cout.tie(0);↵
    fill(rev, rev + maxn, -1);↵
    fill(a, a + maxn, -1);↵
    int q;↵
    cin >> q;↵
    int ptr = -1;↵
    vector<pair<pair<int, int>, int>> changes;↵
    while (q--) {↵
        char t;↵
        cin >> t;↵
        if (t == '?') {↵
            cout << get(ptr) << endl;↵
        } else if (t == '+') {↵
            int x;↵
            cin >> x;↵
            int mem = a[ptr + 1];↵
            if (a[ptr + 1] != -1) {↵
                if (ids[a[ptr + 1]].size()) {↵
                    upd(*ids[a[ptr + 1]].begin(), -1);↵
                    ids[a[ptr + 1]].erase(ptr + 1);↵
                }↵
                if (ids[a[ptr + 1]].size()) {↵
                    upd(*ids[a[ptr + 1]].begin(), 1);↵
                }↵
            }↵
            a[ptr + 1] = x;↵
            if (a[ptr + 1] != -1) {↵
                if (ids[a[ptr + 1]].size()) {↵
                    upd(*ids[a[ptr + 1]].begin(), -1);↵
                }↵
                ids[x].insert(ptr + 1);↵
                if (ids[a[ptr + 1]].size()) {↵
                    upd(*ids[a[ptr + 1]].begin(), 1);↵
                }↵
            }↵
            ++ptr;↵
            changes.push_back({ { 1, mem }, -1 });↵
        } else if (t == '-') {↵
            int k;↵
            cin >> k;↵
            ptr -= k;↵
            changes.push_back({ { -1, k }, -1 });↵
        } else {↵
            if (changes.back().first.first == 1) {↵
                if (a[ptr] != -1) {↵
                    if (ids[a[ptr]].size()) {↵
                        upd(*ids[a[ptr]].begin(), -1);↵
                        ids[a[ptr]].erase(ptr);↵
                    }↵
                    if (ids[a[ptr]].size()) {↵
                        upd(*ids[a[ptr]].begin(), 1);↵
                    }↵
                }↵
                a[ptr] = changes.back().first.second;↵
                --ptr;↵
                if (a[ptr + 1] != -1) {↵
                    if (ids[a[ptr + 1]].size()) {↵
                        upd(*ids[a[ptr + 1]].begin(), -1);↵
                    }↵
                    ids[a[ptr + 1]].insert(ptr + 1);↵
                    if (ids[a[ptr + 1]].size()) {↵
                        upd(*ids[a[ptr + 1]].begin(), 1);↵
                    }↵
                }↵
            } else {↵
                ptr += changes.back().first.second;↵
            }↵
            changes.pop_back();↵
        }↵
    }↵
}↵
~~~~~↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru9 Russian pakhomovee 2023-08-16 00:57:15 22 Мелкая правка: '];\n r.push_back(1 - d);\n ' -> '];\n r.insert(r.begin(), 1 - d);\n '
en18 English pakhomovee 2023-08-16 00:48:46 22 Tiny change: '];\n r.push_back(1 - d);\n ' -> '];\n r.insert(r.begin(), 1 - d);\n '
ru8 Russian pakhomovee 2023-08-15 21:11:33 12 Мелкая правка: 'ментариях)~--- это то, ' -> 'ментариях) - это то, '
ru7 Russian pakhomovee 2023-08-15 21:11:08 18 Мелкая правка: 'ачи E2, а jiangly написал т' -> 'ачи E2, а [user:jiangly] написал т'
ru6 Russian pakhomovee 2023-08-15 21:10:53 412
en17 English pakhomovee 2023-08-15 21:08:33 1 Tiny change: 'er details see [subm' -> 'er details, see [subm'
en16 English pakhomovee 2023-08-15 21:07:49 3 Tiny change: '*Note:** After about 20 ' -> '*Note:** At about 20 '
en15 English pakhomovee 2023-08-15 21:07:30 417
ru5 Russian pakhomovee 2023-08-15 20:44:52 2
en14 English pakhomovee 2023-08-15 20:41:36 2
en13 English pakhomovee 2023-08-15 20:06:22 34 Tiny change: ');\n\n sort(r.begin(), r.end());\n\n ' -> ');\n\n '
ru4 Russian pakhomovee 2023-08-15 20:05:55 33 Мелкая правка: ');\n\n sort(r.begin(), r.end());\n\n ' -> ');\n\n '
en12 English pakhomovee 2023-08-15 19:44:49 12210
ru3 Russian pakhomovee 2023-08-15 19:44:14 1 (опубликовано)
ru2 Russian pakhomovee 2023-08-15 19:43:17 8087
en11 English pakhomovee 2023-08-15 19:39:50 1 (published)
en10 English pakhomovee 2023-08-15 19:38:48 145
en9 English pakhomovee 2023-08-15 19:36:52 33
en8 English pakhomovee 2023-08-15 19:36:22 42
en7 English pakhomovee 2023-08-15 19:35:45 80
en6 English pakhomovee 2023-08-15 19:34:49 5
en5 English pakhomovee 2023-08-15 19:32:54 31
en4 English pakhomovee 2023-08-15 19:31:41 70
en3 English pakhomovee 2023-08-15 19:30:17 7022
en2 English pakhomovee 2023-08-15 19:27:58 8768
ru1 Russian pakhomovee 2023-08-15 19:22:49 813 Первая редакция перевода на Русский (сохранено в черновиках)
en1 English pakhomovee 2023-08-15 19:22:23 800 Initial revision (saved to drafts)