Submission #1032535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032535		tvladm2009	Autobahn (COI21_autobahn)	C++17	0 / 100	1 ms	604 KiB

autobahn

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define int ll

const int N = 1e5 + 7;

int n, k, x;
int l[N], r[N], t[N];
map<int, int> guys, taxes;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> x;
    set<int> events;
    for (int i = 1; i <= n; ++i) {
        cin >> l[i] >> t[i] >> r[i];
        guys[l[i]]++;
        guys[r[i] + 1]--;
        events.insert(l[i]);
        events.insert(r[i] + 1);
        if (l[i] + t[i] <= r[i]) {
            taxes[l[i] + t[i]]++;
            taxes[r[i] + 1]--;
            events.insert(l[i] + t[i]);
            events.insert(r[i] + 1);
        }
    }

    vector<array<int, 3>> inter;
    int prev = 0, s = 0, p = 0;
    for (auto t : events) {
        int profit = p >= k ? s : 0; 
        if (t != *events.begin()) {
            inter.push_back({prev, t - 1, profit});
        }

        s += taxes[t];
        p += guys[t];
        
        prev = t;
    }

    auto dist = [&](int l, int r) {
        return inter[r][1] - inter[l][0] + 1;
    };
    
    vector<ll> cost(inter.size());
    for (int i = 0; i < inter.size(); ++i) cost[i] = (i == 0 ? 0 : cost[i - 1]) + (inter[i][1] - inter[i][0] + 1) * inter[i][2];
    auto get_profit = [&](int l, int r) {
        if (l == 0) return cost[r];
        return cost[r] - cost[l - 1];
    };

    ll ans = 0;
    for (int i = 0; i < inter.size(); ++i) {
        int l = i, r = inter.size() - 1, sol = i - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (dist(i, m) <= x) {
                sol = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        ll cur = 0;
        if (sol == inter.size() - 1) {
            cur = get_profit(i, inter.size() - 1);
        } else {
            cur = get_profit(i, sol);
            int rem = x - dist(i, sol);
            assert(rem <= inter[sol + 1][1] - inter[sol + 1][0] + 1);
            cur += inter[sol + 1][2] * rem;
        }
        ans = max(ans, cur);
    }
    for (int i = 0; i < inter.size(); ++i) {
        int l = 0, r = inter.size() - 1, sol = i + 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (dist(m, i) <= x) {
                sol = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        ll cur = 0;
        if (sol == 0) {
            cur = get_profit(0, i);
        } else {
            cur = get_profit(sol, i);
            int rem = x - dist(sol, i);
            assert(rem <= inter[sol - 1][1] - inter[sol - 1][0] + 1);
            cur += inter[sol - 1][2] * rem;
        }
        ans = max(ans, cur);
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:53:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < inter.size(); ++i) cost[i] = (i == 0 ? 0 : cost[i - 1]) + (inter[i][1] - inter[i][0] + 1) * inter[i][2];
      |                     ~~^~~~~~~~~~~~~~
autobahn.cpp:60:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < inter.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
autobahn.cpp:72:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if (sol == inter.size() - 1) {
      |             ~~~~^~~~~~~~~~~~~~~~~~~
autobahn.cpp:82:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < inter.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

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