#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Observation #1 : We can use line sweep, using positions l, l + t, and r
// positions l (cnt++)
// positions l + t (debt++)
// positions r (cnt--, debt--)
// Observation #2 : Happy Hour either starts at a position, or ends at a position
// So there are a total of 9 * N positions
const int MX = 1e5 + 10;
int N, K, X, l[MX], r[MX], t[MX];
vector<int> v;
int cnt[9 * MX], dt[9 * MX]; ll pref[9 * MX];
void chmax(ll& a, ll b){
if(b > a) a = b;
}
void add(int val){
v.push_back(val);
v.push_back(val - X);
v.push_back(val + X);
}
inline int index(int val){
vector<int>::iterator it = lower_bound(v.begin(), v.end(), val);
if(it == v.end()) return -1;
return (*it) == val ? (it - v.begin()) : -1;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
cin >> N >> K >> X;
for(int i = 0; i < N; i++){
cin >> l[i] >> t[i] >> r[i];
t[i] = min(l[i] + t[i], r[i] + 1);
add(l[i]); add(t[i]); add(r[i] + 1);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
int M = v.size();
for(int i = 0; i < N; i++){
int _l = index(l[i]), _t = index(t[i]), _r = index(r[i] + 1);
cnt[_l]++; dt[_t]++; cnt[_r]--; dt[_r]--;
}
for(int i = 1; i < M; i++){
cnt[i] += cnt[i - 1]; dt[i] += dt[i - 1];
}
for(int i = 1; i < M; i++){
pref[i] = pref[i - 1] + 1ll * (v[i] - v[i - 1]) * (cnt[i - 1] >= K ? dt[i - 1] : 0);
}
ll ans = 0;
for(int i = 0; i < M; i++){
int nxt = index(v[i] + X);
if(nxt != -1) chmax(ans, pref[nxt] - pref[i]);
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
328 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
328 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
2 ms |
460 KB |
Output is correct |
| 13 |
Correct |
2 ms |
460 KB |
Output is correct |
| 14 |
Correct |
2 ms |
460 KB |
Output is correct |
| 15 |
Correct |
2 ms |
460 KB |
Output is correct |
| 16 |
Correct |
2 ms |
472 KB |
Output is correct |
| 17 |
Correct |
2 ms |
460 KB |
Output is correct |
| 18 |
Correct |
2 ms |
460 KB |
Output is correct |
| 19 |
Correct |
2 ms |
460 KB |
Output is correct |
| 20 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
328 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
2 ms |
460 KB |
Output is correct |
| 13 |
Correct |
2 ms |
460 KB |
Output is correct |
| 14 |
Correct |
2 ms |
460 KB |
Output is correct |
| 15 |
Correct |
2 ms |
460 KB |
Output is correct |
| 16 |
Correct |
2 ms |
472 KB |
Output is correct |
| 17 |
Correct |
2 ms |
460 KB |
Output is correct |
| 18 |
Correct |
2 ms |
460 KB |
Output is correct |
| 19 |
Correct |
2 ms |
460 KB |
Output is correct |
| 20 |
Correct |
2 ms |
460 KB |
Output is correct |
| 21 |
Correct |
266 ms |
21880 KB |
Output is correct |
| 22 |
Correct |
252 ms |
21784 KB |
Output is correct |
| 23 |
Correct |
260 ms |
21716 KB |
Output is correct |
| 24 |
Correct |
241 ms |
21704 KB |
Output is correct |
| 25 |
Correct |
268 ms |
21796 KB |
Output is correct |
| 26 |
Correct |
246 ms |
21776 KB |
Output is correct |
| 27 |
Correct |
266 ms |
21740 KB |
Output is correct |
| 28 |
Correct |
234 ms |
21720 KB |
Output is correct |
| 29 |
Correct |
239 ms |
21856 KB |
Output is correct |
