Submission #1253036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253036		Semen07	Rope (JOI17_rope)	C++20	55 / 100	2596 ms	127200 KiB

rope

#include <bits/stdc++.h>

int main() {
    // freopen("main.in", "r", stdin);
    // freopen("main.out", "w", stdout);
    int n;
    size_t m;
    std::cin >> n >> m;
    std::vector<size_t> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        --a[i];
    }
    std::vector<int> all_ans(m);
    std::map<std::pair<size_t, size_t>, int> cnt2;
    std::vector<int> cnt(m, 0);
    for (int i = 0; i < n; i += 2) {
        if (i + 1 < n) {
            cnt2[{a[i], a[i + 1]}]++, cnt[a[i]]++;
            if (a[i] != a[i + 1]) cnt2[{a[i + 1], a[i]}]++, cnt[a[i + 1]]++;
        } else {
            cnt[a[i]]++;
        }
    }
    std::vector<std::set<std::pair<int, size_t>>> d2(m);
    std::set<std::pair<int, size_t>> d;
    for (size_t i = 0; i < m; ++i) {
        d.emplace(cnt[i] + cnt2[{i, i}], i);
    }
    for (int i = 0; i + 1 < n; i += 2) {
        if (a[i] != a[i + 1]) {
            d2[a[i]].emplace(cnt[a[i + 1]] + cnt2[{a[i + 1], a[i + 1]}] - cnt2[{a[i], a[i + 1]}], a[i + 1]);
            d2[a[i + 1]].emplace(cnt[a[i]] + cnt2[{a[i], a[i]}] - cnt2[{a[i], a[i + 1]}], a[i]);
        }
    }
    int base_ans = n;
    for (size_t f = 0; f < m; ++f) {
        base_ans = std::min(base_ans, n - cnt2[{f, f}] - cnt[f]);
    }
    for (size_t f = 0; f < m; ++f) {
        int ans = base_ans;
        if (!d2[f].empty()) ans = std::min(ans, n - cnt[f] - cnt2[{f, f}] - (--d2[f].end())->first);
        for (auto [x, y]: d2[f]) {
            d.erase({cnt[y] + cnt2[{y, y}], y});
        }
        d.erase({cnt[f] + cnt2[{f, f}], f});
        if (!d.empty()) ans = std::min(ans, n - cnt[f] - cnt2[{f, f}] - (--d.end())->first);
        d.insert({cnt[f] + cnt2[{f, f}], f});
        for (auto [x, y]: d2[f]) {
            d.insert({cnt[y] + cnt2[{y, y}], y});
        }
        all_ans[f] = ans;
    }
    cnt2.clear();
    cnt.assign(m, 0);
    for (int i = -1; i < n; i += 2) {
        if (i + 1 < n && i > 0) {
            cnt2[{a[i], a[i + 1]}]++, cnt[a[i]]++;
            if (a[i] != a[i + 1]) cnt2[{a[i + 1], a[i]}]++, cnt[a[i + 1]]++;
        } else {
            if (i + 1 == n) cnt[a[i]]++;
            else cnt[a[i + 1]]++;
        }
    }
    d2.assign(m, {});
    d.clear();
    for (size_t i = 0; i < m; ++i) {
        d.emplace(cnt[i] + cnt2[{i, i}], i);
    }
    for (int i = 1; i + 1 < n; i += 2) {
        if (a[i] != a[i + 1]) {
            d2[a[i]].emplace(cnt[a[i + 1]] + cnt2[{a[i + 1], a[i + 1]}] - cnt2[{a[i], a[i + 1]}], a[i + 1]);
            d2[a[i + 1]].emplace(cnt[a[i]] + cnt2[{a[i], a[i]}] - cnt2[{a[i], a[i + 1]}], a[i]);
        }
    }
    base_ans = n;
    for (size_t f = 0; f < m; ++f) {
        base_ans = std::min(base_ans, n - cnt2[{f, f}] - cnt[f]);
    }
    for (size_t f = 0; f < m; ++f) {
        int ans = base_ans;
        if (!d2[f].empty()) ans = std::min(ans, n - cnt[f] - cnt2[{f, f}] - (--d2[f].end())->first);
        for (auto [x, y]: d2[f]) {
            d.erase({cnt[y] + cnt2[{y, y}], y});
        }
        d.erase({cnt[f] + cnt2[{f, f}], f});
        if (!d.empty()) ans = std::min(ans, n - cnt[f] - cnt2[{f, f}] - (--d.end())->first);
        d.insert({cnt[f] + cnt2[{f, f}], f});
        for (auto [x, y]: d2[f]) {
            d.insert({cnt[y] + cnt2[{y, y}], y});
        }
        all_ans[f] = std::min(all_ans[f], ans);
        std::cout << all_ans[f] << '\n';
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20