Submission #997904

#	Time	Username	Problem	Language	Result	Execution time	Memory
997904		piOOE	Autobahn (COI21_autobahn)	C++17	100 / 100	57 ms	12808 KiB

autobahn

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, x;
    cin >> n >> k >> x;

    vector<pair<int, int>> events;
    for (int i = 0; i < n; ++i) {
        int l, r, t;
        cin >> l >> t >> r;
        r += 1;
        events.push_back({l, -1});
        events.push_back({r, 1});
        events.push_back({min(r, l + t), 0});
    }
    sort(events.begin(), events.end());

    int alive = 0, pay = 0, lastx = -1;
    vector<int> a, c;
    for (auto [dx, t] : events) {
        if (lastx != dx) {
            if (lastx != -1) {
                a.push_back(lastx);
                c.push_back(alive >= k ? pay : 0);
            }
            lastx = dx;
        }
        if (t == -1) {
            alive += 1;
        } else if (t == 0) {
            pay += 1;
        } else {
            alive -= 1, pay -= 1;
        }
    }
    a.push_back(events.back().first);
//    for (int i = 0; i < c.size(); ++i) {
//        cout << a[i] << " " << c[i] << endl;
//    }
//    cout << a.back() << endl;

    ll ans = 0;
    for (int _ = 0; _ < 2; ++_) {
        ll sum = 0;
        for (int i = 0, j = 0; i + 1 < a.size(); ++i) {
            j = max(j, i);
            while (j + 1 < a.size() && a[j + 1] - a[i] <= x) {
                sum += 1LL * c[j] * (a[j + 1] - a[j]);
                j += 1;
            }
            int can = max(0, x - (a[j] - a[i]));
            ans = max(ans, sum + (j + 1 < a.size() ? can * 1LL * c[j] : 0LL));
            if (i + 1 <= j) {
                sum -= c[i] * 1LL * (a[i + 1] - a[i]);
            }
        }
        reverse(a.begin(), a.end());
        reverse(c.begin(), c.end());
        for (int &ty : a) {
            ty = -ty;
        }
    }
    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:51:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0, j = 0; i + 1 < a.size(); ++i) {
      |                                ~~~~~~^~~~~~~~~~
autobahn.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             while (j + 1 < a.size() && a[j + 1] - a[i] <= x) {
      |                    ~~~~~~^~~~~~~~~~
autobahn.cpp:58:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             ans = max(ans, sum + (j + 1 < a.size() ? can * 1LL * c[j] : 0LL));
      |                                   ~~~~~~^~~~~~~~~~

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