oj.uz

Submission #1032538

# Submission time Handle Problem Language Result Execution time Memory
1032538 2024-07-24T01:06:37 Z tvladm2009 Autobahn (COI21_autobahn) C++17
100 / 100
 481 ms 68880 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 352 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 464 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 352 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 464 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 628 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 608 KB Output is correct
20 Correct 1 ms 608 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 352 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 464 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 628 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 608 KB Output is correct
20 Correct 1 ms 608 KB Output is correct
21 Correct 478 ms 68748 KB Output is correct
22 Correct 432 ms 68852 KB Output is correct
23 Correct 480 ms 68724 KB Output is correct
24 Correct 481 ms 68848 KB Output is correct
25 Correct 463 ms 68764 KB Output is correct
26 Correct 458 ms 68880 KB Output is correct
27 Correct 423 ms 68852 KB Output is correct
28 Correct 431 ms 68756 KB Output is correct
29 Correct 407 ms 68852 KB Output is correct