This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |