Submission #420401

#TimeUsernameProblemLanguageResultExecution timeMemory
420401rama_pangAutobahn (COI21_autobahn)C++17
100 / 100
358 ms33528 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int N, K, X; cin >> N >> K >> X; vector<int> L(N), T(N), R(N); map<int, pair<int, int>> events; for (int i = 0; i < N; i++) { cin >> L[i] >> T[i] >> R[i]; events[L[i]].first += 1; events[R[i] + 1].first -= 1; if (L[i] + T[i] <= R[i]) { events[L[i] + T[i]].second += 1; events[R[i] + 1].second -= 1; } } int sumBad = 0; int sumStay = 0; int last = 0; vector<array<int, 3>> inter; for (auto [t, ev] : events) { if (sumStay >= K) { inter.push_back({last, t - 1, sumBad}); } last = t; sumStay += ev.first; sumBad += ev.second; } // Find length K with maximum inter score vector<int> coords; for (auto x : inter) { coords.emplace_back(x[0] - 1); coords.emplace_back(x[0] + X - 1); coords.emplace_back(x[1] - X); coords.emplace_back(x[1]); } sort(begin(coords), end(coords)); coords.resize(unique(begin(coords), end(coords)) - begin(coords)); vector<long long> coordAns(coords.size()); int ptr = 0; long long overlap = 0; for (int cid = 0; cid < int(coords.size()); cid++) { while (ptr < int(inter.size()) && inter[ptr][1] < coords[cid]) { overlap += 1ll * (inter[ptr][1] - inter[ptr][0] + 1) * inter[ptr][2]; ptr += 1; } coordAns[cid] = overlap; if (ptr < int(inter.size()) && inter[ptr][0] <= coords[cid]) { coordAns[cid] += 1ll * (coords[cid] - inter[ptr][0] + 1) * inter[ptr][2]; } } long long ans = 0; for (auto x : inter) { { int it1 = lower_bound(begin(coords), end(coords), x[0] - 1) - begin(coords); int it2 = lower_bound(begin(coords), end(coords), x[0] + X - 1) - begin(coords); ans = max(ans, coordAns[it2] - coordAns[it1]); } { int it1 = lower_bound(begin(coords), end(coords), x[1] - X) - begin(coords); int it2 = lower_bound(begin(coords), end(coords), x[1]) - begin(coords); ans = max(ans, coordAns[it2] - coordAns[it1]); } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...