Submission #636088

#	Time	Username	Problem	Language	Result	Execution time	Memory
636088		eecs	Autobahn (COI21_autobahn)	C++17	100 / 100	343 ms	32352 KiB

autobahn

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k, x;
    cin >> n >> k >> x;
    map<int, array<int, 2>> ev;
    for (int i = 0, l, t, r; i < n; i++) {
        cin >> l >> t >> r;
        ev[l][0]++, ev[r + 1][0]--;
        if (l + t <= r) ev[l + t][1]++, ev[r + 1][1]--;
    }
    vector<array<int, 3>> inter;
    int stay = 0, bad = 0, lst = 0;
    for (auto [t, p] : ev) {
        if (stay >= k) inter.push_back({lst, t - 1, bad});
        stay += p[0], bad += p[1], lst = t;
    }
    vector<int> cand;
    for (auto &p : inter) {
        cand.insert(cand.end(), {p[0] - 1, p[0] + x - 1, p[1] - x, p[1]});
    }
    sort(cand.begin(), cand.end());
    cand.resize(unique(cand.begin(), cand.end()) - cand.begin());
    vector<ll> res(cand.size());
    ll overlap = 0;
    for (int i = 0, j = 0; i < cand.size(); i++) {
        for (; j < inter.size() && inter[j][1] < cand[i]; j++) {
            overlap += 1LL * (inter[j][1] - inter[j][0] + 1) * inter[j][2];
        }
        res[i] = overlap;
        if (j < inter.size() && inter[j][0] <= cand[i]) {
            res[i] += 1LL * (cand[i] - inter[j][0] + 1) * inter[j][2];
        }
    }
    ll ans = 0;
    for (auto &p : inter) {
        int it1 = lower_bound(cand.begin(), cand.end(), p[0] - 1) - cand.begin();
        int it2 = lower_bound(cand.begin(), cand.end(), p[0] + x - 1) - cand.begin();
        ans = max(ans, res[it2] - res[it1]);
        it1 = lower_bound(cand.begin(), cand.end(), p[1] - x) - cand.begin();
        it2 = lower_bound(cand.begin(), cand.end(), p[1]) - cand.begin();
        ans = max(ans, res[it2] - res[it1]);
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:30:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0, j = 0; i < cand.size(); i++) {
      |                            ~~^~~~~~~~~~~~~
autobahn.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (; j < inter.size() && inter[j][1] < cand[i]; j++) {
      |                ~~^~~~~~~~~~~~~~
autobahn.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (j < inter.size() && inter[j][0] <= cand[i]) {
      |             ~~^~~~~~~~~~~~~~

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