#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;
inline long long combine(long long a, long long b){
return a+b;
}
struct node{
int s,e,m;
node *l,*r;
long long v;
long long lazyUpd;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v(0),lazyUpd(0){
}
inline void inst(){
if(l==NULL) l=new node(s,m);
if(r==NULL) r=new node(m+1,e);
}
void self_add(int x){
v+=(e-s+1)*x;
lazyUpd+=x;
}
void forceProp(){
if(s==e) return;
if(lazyUpd){
l->self_add(lazyUpd),r->self_add(lazyUpd);
lazyUpd=0;
}
}
void rangeUpd(int x, int y, int c){
if(x<=s&&y>=e){
self_add(c);
return;
}
inst();
forceProp();
if(x<=m) l->rangeUpd(x,y,c);
if(y>m){
r->rangeUpd(x,y,c);
}
v=combine(l->v,r->v);
}
long long query(int x, int y){
if(x<=s&&y>=e){
return v;
}
inst();
forceProp();
if(y<=m) return l->query(x,y);
if(x>m) return r->query(x,y);
return combine(l->query(x,m),r->query(m+1,y));
}
};
struct event{
int type, sign;
event(int tt, int ss):type(tt),sign(ss){}
};
void solve(){
int n,k,m;
cin >> n >> k >> m;
int temp,temp2,temp3;
map<int,vector<int>>mp;
for(int x=0;x<n;x++){
cin >> temp >> temp2 >> temp3;
//event hold(0,1);
//event hold2(0,-1);
mp[temp].push_back(1);
mp[temp+temp2].push_back(2);
if(temp+temp2<=temp3){
//event hold3(1,1);
//event hold4(1,-1);
mp[temp+temp2].push_back(3);
mp[temp3+1].push_back(4);
}
}
int last=0;
int car=0;
int unpaid=0;
//node st(0,1e9+5);
vector<int>v;
deque<pair<pii,int>>d;
for(auto index:mp){
//show(index.first,index.first);
if(car>=k){
//st.rangeUpd(last,index.first-1,unpaid);
d.push_back({{last,index.first-1},unpaid});
//d2.push_back({{last,index.first-1},unpaid});
v.push_back(index.first-1);
v.push_back(last+m-1);
}
for(auto it:index.second){
if(it==1||it==2){
//paid
if(it==1) car++;
else car--;
}
else{
//unpaid
if(it==3){
car++;
unpaid++;
}
else{
car--;
unpaid--;
}
}
}
last=index.first;
}
long long best=0;
long long counter=0;
int ptr=0;
//for(auto it:d){
//cout << it.first.first << " " << it.first.second << " " << it.second << endl;
//}
for(int x=0;x<(int)d.size();x++){
counter+=(d[x].first.second-d[x].first.first+1)*d[x].second;
int l=d[x].first.second-m+1;
while(ptr<(int)d.size()&&l>d[ptr].first.second){
counter-=(d[ptr].first.second-d[ptr].first.first+1)*d[ptr].second;
ptr++;
}
int add=0;
if(l>=d[ptr].first.first){
add=-(l-d[ptr].first.first);
}
best=max(best,counter+add);
//show(counter,counter);
}
//show(best,best);
ptr=(int)d.size()-1;
counter=0;
for(int x=(int)d.size()-1;x>=0;x--){
counter+=(d[x].first.second-d[x].first.first+1)*d[x].second;
int r=d[x].first.first+m-1;
while(ptr>=0&&r<d[ptr].first.first){
counter-=(d[ptr].first.second-d[ptr].first.first+1)*d[ptr].second;
ptr--;
}
int add=0;
if(r<=d[ptr].first.second){
add=-(d[ptr].first.second-r);
}
best=max(best,counter+add);
}
cout << best;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
352 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
352 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
352 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
