#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, x, len;
ll l[300002], t[300002], r[300002];
vector<ll> point = {-1'000'000'000, 1'000'000'000};
ll cnt[300002], sum[300002], w[300002], wsum[300002]; /// 사람 수, 벌금 사람 수
ll ans;
int main(){
scanf("%lld %lld %lld", &n, &k, &x);
for(ll i=1; i<=n; i++){
scanf("%lld %lld %lld", &l[i], &t[i], &r[i]);
r[i]++;
point.push_back(l[i]), point.push_back(r[i]);
if(l[i] + t[i] < r[i]) point.push_back(l[i] + t[i]);
}
sort(point.begin(), point.end());
point.erase(unique(point.begin(), point.end()), point.end());
len = (ll)point.size();
for(ll i=1; i<=n; i++){
ll lp = lower_bound(point.begin(), point.end(), l[i]) - point.begin();
ll mp = lower_bound(point.begin(), point.end(), min(r[i], l[i] + t[i])) - point.begin();
ll rp = lower_bound(point.begin(), point.end(), r[i]) - point.begin();
cnt[lp]++, cnt[rp]--;
sum[mp]++, sum[rp]--;
}
for(ll i=0; i<len-1; i++){
if(i) cnt[i] += cnt[i-1], sum[i] += sum[i-1];
}
for(ll i=0; i<len-1; i++){
if(cnt[i] < k) sum[i] = 0;
w[i] = sum[i] * (point[i+1] - point[i]);
wsum[i] = (i ? wsum[i-1] : 0LL) + w[i];
}
ll pnt;
for(ll i=1; i<len; i++){
pnt = upper_bound(point.begin(), point.end(), point[i] + x - 1) - 1 - point.begin();
ans = max(ans, wsum[pnt-1] - wsum[i-1] + (point[i] + x - point[pnt]) * sum[pnt]);
}
for(ll i=0; i<len-1; i++){
pnt = upper_bound(point.begin(), point.end(), point[i+1] - x) - 1 - point.begin();
if(pnt) ans = max(ans, wsum[i] - wsum[pnt] + (point[pnt+1] - (point[i+1] - x)) * sum[pnt]);
}
printf("%lld", ans);
}
Compilation message
autobahn.cpp: In function 'int main()':
autobahn.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | scanf("%lld %lld %lld", &n, &k, &x);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
autobahn.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | scanf("%lld %lld %lld", &l[i], &t[i], &r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
468 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
460 KB |
Output is correct |
| 17 |
Correct |
1 ms |
456 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
468 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
460 KB |
Output is correct |
| 17 |
Correct |
1 ms |
456 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
460 KB |
Output is correct |
| 21 |
Correct |
130 ms |
17332 KB |
Output is correct |
| 22 |
Correct |
142 ms |
17168 KB |
Output is correct |
| 23 |
Correct |
124 ms |
17140 KB |
Output is correct |
| 24 |
Correct |
119 ms |
17204 KB |
Output is correct |
| 25 |
Correct |
118 ms |
17172 KB |
Output is correct |
| 26 |
Correct |
117 ms |
17280 KB |
Output is correct |
| 27 |
Correct |
115 ms |
17172 KB |
Output is correct |
| 28 |
Correct |
115 ms |
17248 KB |
Output is correct |
| 29 |
Correct |
113 ms |
17204 KB |
Output is correct |
