Submission #997971

#	Time	Username	Problem	Language	Result	Execution time	Memory
997971		Qwerty1232	Autobahn (COI21_autobahn)	C++17	100 / 100	133 ms	9164 KiB

autobahn

#include <bits/stdc++.h>

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k, x;
    std::cin >> n >> k >> x;
    std::vector<std::array<int, 3>> input(n);
    for (auto& [l, t, r] : input) {
        std::cin >> l >> t >> r;
        r++;
    }

    std::vector<int> all;
    for (auto& [l, t, r] : input) {
        all.push_back(l);
        all.push_back(l + std::min(t, r - l));
        all.push_back(r);
    }
    std::sort(all.begin(), all.end());
    all.erase(std::unique(all.begin(), all.end()), all.end());

    int m = all.size() - 1;
    std::vector<int> cnt(m + 1), cnt_ch(m + 1);
    for (auto [l, t, r] : input) {
        int lc = l + std::min(t, r - l);
        int it1 = std::lower_bound(all.begin(), all.end(), l) - all.begin();
        int it2 = std::lower_bound(all.begin(), all.end(), lc) - all.begin();
        int it3 = std::lower_bound(all.begin(), all.end(), r) - all.begin();
        cnt[it1]++;
        cnt[it3]--;
        cnt_ch[it2]++;
        cnt_ch[it3]--;
    }

    for (int i = 0, c1 = 0, c2 = 0; i < m; i++) {
        c1 += cnt[i];
        cnt[i] = c1;
        c2 += cnt_ch[i];
        cnt_ch[i] = c2;
        cnt_ch[i] *= cnt[i] >= k;
    }

    std::vector<int64_t> prf(m + 1);
    for (int i = 0; i < m; i++) {
        prf[i + 1] = prf[i] + cnt_ch[i] * int64_t(all[i + 1] - all[i]);
    }

    int64_t ans = 0;
    auto get_prf = [&](int p) {
        p = std::max(p, all[0]);
        auto it = std::upper_bound(all.begin(), all.end(), p) - all.begin();
        return prf[it - 1] + cnt_ch[it - 1] * int64_t(p - all[it - 1]);
    };
    auto upd = [&](int l, int r) {
        int64_t res = get_prf(r) - get_prf(l);
        ans = std::max(ans, res);
    };
    for (int i = 0; i <= m; i++) {
        upd(all[i], all[i] + x);
        upd(all[i] - x, all[i]);
    }

    std::cout << ans << "\n";

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50