#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> ii;
int N,K,X;
vector<ii> events,overtime,charge;
int32_t main() {
#ifdef ACM
freopen("input","r",stdin);
#endif
cin>>N>>K>>X;
int l,t,r;
for(int i=0;i<N;i++) {
cin>>l>>t>>r;
if(l+t<=r) {
overtime.push_back({l+t,1});
overtime.push_back({r+1,-1});
}
events.push_back({l,1});
events.push_back({r+1,-1});
}
sort(events.begin(),events.end());
int people=0,pivot;
for(ii event:events) {
people+=event.second;
if(event.second==1&&people==K)
pivot=event.first;
else if(event.second==-1&&people==K-1) {
overtime.push_back({pivot,2});
overtime.push_back({event.first,-2});
}
}
sort(overtime.begin(),overtime.end());
//for(ii tmp:overtime)
// cerr<<tmp.first<<' '<<tmp.second<<'\n';
int numOvertime=0;
bool overload=false;
for(ii event:overtime) {
if(abs(event.second)==1)
numOvertime+=event.second;
else
overload=(event.second==2);
if(overload) {
if(charge.size()>0&&charge.back().first==event.first)
charge.back().second=numOvertime;
else
charge.push_back({event.first,numOvertime});
}
else if(charge.size()>0&&charge.back().first==event.first)
charge.back().second=0;
else
charge.push_back({event.first,0});
}
//for(ii tmp:charge)
// cerr<<tmp.first<<' '<<tmp.second<<'\n';
vector<int> S(charge.size());
for(int i=0;i<charge.size()-1;i++) {
S[i]=(charge[i+1].first-charge[i].first)*charge[i].second;
if(i>0)
S[i]+=S[i-1];
}
int cur=0,rs=0;
for(int i=0;i<charge.size()-1;i++) {
while(cur<charge.size()-1&&charge[cur+1].first<=charge[i].first+X-1)
cur++;
int sum=0;
if(cur>0)
sum=S[cur-1]-(i==0?0:S[i-1]);
sum+=(charge[i].first+X-charge[cur].first)*charge[cur].second;
rs=max(rs,sum);
}
cur=0;
for(int i=0;i<charge.size()-1;i++) {
while(cur<i&&charge[cur].first+X<charge[i+1].first)
cur++;
int sum=S[i]-S[cur];
if(cur>0)
sum+=(charge[cur].first-charge[i+1].first+X)*charge[cur-1].second;
rs=max(rs,sum);
}
cout<<rs;
}
Compilation message
autobahn.cpp: In function 'int32_t main()':
autobahn.cpp:59:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i=0;i<charge.size()-1;i++) {
| ~^~~~~~~~~~~~~~~~
autobahn.cpp:65:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<charge.size()-1;i++) {
| ~^~~~~~~~~~~~~~~~
autobahn.cpp:66:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | while(cur<charge.size()-1&&charge[cur+1].first<=charge[i].first+X-1)
| ~~~^~~~~~~~~~~~~~~~
autobahn.cpp:75:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i=0;i<charge.size()-1;i++) {
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 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 |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
292 KB |
Output is correct |
| 8 |
Correct |
1 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 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 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 |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
292 KB |
Output is correct |
| 8 |
Correct |
1 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 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 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 |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
292 KB |
Output is correct |
| 8 |
Correct |
1 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 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
