Submission #1032538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032538		tvladm2009	Autobahn (COI21_autobahn)	C++17	100 / 100	481 ms	68880 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 > r) return 0LL;
        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 - (inter[sol + 1][0] - inter[i][0]);
            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 - (inter[i][1] - inter[sol - 1][1]);
            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:61: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]
   61 |     for (int i = 0; i < inter.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
autobahn.cpp:73: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]
   73 |         if (sol == inter.size() - 1) {
      |             ~~~~^~~~~~~~~~~~~~~~~~~
autobahn.cpp:83: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]
   83 |     for (int i = 0; i < inter.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

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