Submission #1253272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253272		Semen07	Rope (JOI17_rope)	C++20	55 / 100	2597 ms	123656 KiB

rope

#include <bits/stdc++.h>

template<typename T1, typename T2>
struct std::hash<std::pair<T1, T2>> {
    static constexpr size_t p = 1'000'000'009;
    size_t operator()(const std::pair<T1, T2> &obj) const {
        return obj.first * p + obj.second;
    }
};

int n;
size_t m;
std::vector<size_t> a;
std::vector<int> all_ans;
std::unordered_map<std::pair<size_t, size_t>, int> cnt2;
std::vector<int> cnt;

void update(int shift) {
    std::vector<std::set<std::pair<int, size_t>>> d2(m);
    std::vector<std::pair<int, size_t>> d;
    for (size_t i = 0; i < m; ++i) {
        d.emplace_back(cnt[i] + cnt2[{i, i}], i);
    }
    std::sort(d.begin(), d.end());
    std::vector<size_t> di(m);
    for (size_t i = 0; i < m; ++i) {
        di[d[i].second] = i;
    }
    std::vector<int> used(m, 1);
    for (int i = shift; 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]) {
            used[di[y]] = 0;
        }
        used[di[f]] = 0;
        int ind = m - 1;
        while (ind >= 0 && used[ind] == 0) --ind;
        if (ind >= 0) ans = std::min(ans, n - cnt[f] - cnt2[{f, f}] - d[ind].first);
        used[di[f]] = 1;
        for (auto [x, y]: d2[f]) {
            used[di[y]] = 1;
        }
        all_ans[f] = std::min(all_ans[f], ans);
    }
}

int main() {
    // freopen("main.in", "r", stdin);
    // freopen("main.out", "w", stdout);
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
    std::cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        --a[i];
    }
    all_ans.resize(m, n);
    cnt2.clear();
    cnt.assign(m, {});
    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]]++;
        }
    }
    update(0);
    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]]++;
        }
    }
    update(1);
    for (size_t i = 0; i < m; ++i) {
        std::cout << all_ans[i] << '\n';
    }
}

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