Submission #997908

#	Time	Username	Problem	Language	Result	Execution time	Memory
997908		arbuzick	Autobahn (COI21_autobahn)	C++17	100 / 100	94 ms	13244 KiB

autobahn

#include <bits/stdc++.h>

using namespace std;

struct Moment {
    int tm, tp, add;

    Moment(int _tm, int _tp, int _add) {
        tm = _tm, tp = _tp, add = _add;
    }

    bool operator<(Moment b) {
        return tm < b.tm;
    }
};

void solve() {
    int n, k, x;
    cin >> n >> k >> x;
    vector<int> l(n), r(n), t(n);
    vector<Moment> arr;
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> t[i] >> r[i];
        l[i]--;
        arr.emplace_back(l[i], 0, 1);
        arr.emplace_back(r[i], 0, -1);
        if (l[i] + t[i] < r[i]) {
            arr.emplace_back(l[i] + t[i], 1, 1);
            arr.emplace_back(r[i], 1, -1);
        }
    }
    sort(arr.begin(), arr.end());
    int cnt_all = 0, cnt_charged = 0, tm_prv = 0;
    vector<pair<pair<int, int>, int>> segms;
    for (auto [tm, tp, add] : arr) {
        if (cnt_all >= k && cnt_charged != 0) {
            segms.emplace_back(make_pair(tm_prv, tm), cnt_charged);
        }
        if (tp == 0) {
            cnt_all += add;
        } else {
            cnt_charged += add;
        }
        tm_prv = tm;
    }
    vector<long long> pr_sum(segms.size() + 1);
    for (int i = 0; i < (int)segms.size(); ++i) {
        pr_sum[i + 1] = pr_sum[i] + segms[i].second * 1LL * (segms[i].first.second - segms[i].first.first);
    }
    auto get_pr = [&](int r) -> long long {
        int pos = lower_bound(segms.begin(), segms.end(), make_pair(make_pair(r, -1), -1)) - segms.begin();
        long long ans = 0;
        if (pos > 0) {
            ans += pr_sum[pos - 1];
        }
        if (pos > 0) {
            ans += segms[pos - 1].second * 1LL * max(0, min(r, segms[pos - 1].first.second) - segms[pos - 1].first.first);
        }
        return ans;
    };
    auto get_segm = [&](int l, int r) -> long long {
        long long res = get_pr(r) - get_pr(l);
        return get_pr(r) - get_pr(l);
    };
    long long ans = 0;
    for (int i = 0; i < (int)segms.size(); ++i) {
        ans = max(ans, get_segm(segms[i].first.first, segms[i].first.first + x));
        ans = max(ans, get_segm(segms[i].first.second - x, segms[i].first.second));
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

autobahn.cpp: In lambda function:
autobahn.cpp:62:19: warning: unused variable 'res' [-Wunused-variable]
   62 |         long long res = get_pr(r) - get_pr(l);
      |                   ^~~

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