#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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
2 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
2 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
353 ms |
31348 KB |
Output is correct |
| 22 |
Correct |
346 ms |
33328 KB |
Output is correct |
| 23 |
Correct |
355 ms |
33400 KB |
Output is correct |
| 24 |
Correct |
358 ms |
33464 KB |
Output is correct |
| 25 |
Correct |
345 ms |
33280 KB |
Output is correct |
| 26 |
Correct |
343 ms |
33284 KB |
Output is correct |
| 27 |
Correct |
339 ms |
33320 KB |
Output is correct |
| 28 |
Correct |
334 ms |
33472 KB |
Output is correct |
| 29 |
Correct |
342 ms |
33528 KB |
Output is correct |
