#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k, len;
cin >> n >> k >> len;
vector<ar<int, 2>> e;
for (int i=0; i<n; ++i) {
int l, t, r;
cin >> l >> t >> r;
e.push_back({l, 1});
e.push_back({r+1, 2});
if (l+t<=r) {
e.push_back({l+t, 3});
e.push_back({r+1, 4});
}
}
sort(e.begin(), e.end());
vector<ar<int, 3>> seg;
int last=-1, all=0, ex=0;
auto upd=[&](int t) {
if (t==1||t==2)
all+=t==1?1:-1;
else
ex+=t==3?1:-1;
};
for (int i=0; i<e.size(); ++i) {
int x=e[i][0];
if (all>=k&&ex)
seg.push_back({last, x-1, ex});
last=x;
upd(e[i][1]);
while(i+1<e.size()&&e[i+1][0]==x)
upd(e[++i][1]);
}
if (seg.empty()) {
cout << 0;
return 0;
}
vector<ll> pre(seg.size()+1);
for (int i=0; i<seg.size(); ++i)
pre[i+1]=pre[i]+(ll)(seg[i][1]-seg[i][0])*seg[i][2];
ll ans=0;
for (int i=0, j=0, x=seg[0][0]; ;) {
while(j+1<seg.size()&&x+len-1>=seg[j+1][0])
++j;
if (i==j)
ans=max(ans, (ll)(min(seg[i][1], x+len-1)-x+1)*seg[i][2]);
else
ans=max(ans, (pre[j]-pre[i+1])+(ll)(min(seg[j][1], x+len-1)-seg[j][0]+1)*seg[j][2]+(ll)(seg[i][1]-x+1)*seg[i][2]);
if (x+len-1>=seg.back()[1])
break;
int nxt=(x+len-1>=seg[j][1]?seg[j+1][0]:seg[j][1])-len+1;
if (nxt>seg[i][1]||seg[i+1][0]<=nxt) {
++i;
x=seg[i][0];
} else
x=nxt;
}
cout << ans << "\n";
return 0;
}
Compilation message
autobahn.cpp: In function 'int main()':
autobahn.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i=0; i<e.size(); ++i) {
| ~^~~~~~~~~
autobahn.cpp:38:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | while(i+1<e.size()&&e[i+1][0]==x)
| ~~~^~~~~~~~~
autobahn.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i=0; i<seg.size(); ++i)
| ~^~~~~~~~~~~
autobahn.cpp:50:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(j+1<seg.size()&&x+len-1>=seg[j+1][0])
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
