#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
struct event{
int t,x, id;
bool operator < (event b){
if(x == b.x)return t < b.t;
return x < b.x;
}
};
const int MAXN = 1e5+5;
int l[MAXN], t[MAXN], r[MAXN], ans[MAXN*3];
vector<event> e;
set<int> q;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,k,x; cin>>n>>k>>x;
for(int i = 1; i <= n; i++){
cin>>l[i]>>t[i]>>r[i];
t[i] += l[i]; r[i]++;
event fim; fim.t = 1; fim.x = r[i]; fim.id = 0;
if(t[i] >= r[i])fim.id = 1;
e.push_back(fim);
event ini; ini.t = 2; ini.x = l[i]; e.push_back(ini);
if(t[i] < r[i]){event iniP; iniP.t = 3; iniP.x = t[i]; e.push_back(iniP);}
q.insert(r[i]); q.insert(l[i]); q.insert(t[i]);
}
int curi = 0;
for(int i : q){
event temp; temp.x = i-1; temp.t = 4;
temp.id = curi; curi++;
e.push_back(temp);
temp.t = 5; temp.x = i+x+1;
e.push_back(temp);
}
sort(e.begin(),e.end());
int curk = 0, pag = 0, lq = 0, pq = 0;
for(int i = 0; i < sz(e); i++){
if(e[i].t == 1){
curk--;
if(e[i].id == 0)pag--;
}else if(e[i].t == 2)curk++;
else if(e[i].t == 3)pag++;
else if(e[i].t == 4){
int x = pq;
if(curk >= k)x += (e[i].x-lq)*pag;
pq = x; lq = e[i].x;
ans[e[i].id] += x;
}
}
int total = pq;
curk = 0, pag = 0, lq = 0, pq = 0;
for(int i = 0; i < sz(e); i++){
if(e[i].t == 1){
curk--;
if(e[i].id == 0)pag--;
}else if(e[i].t == 2)curk++;
else if(e[i].t == 3)pag++;
else if(e[i].t == 5){
int x = pq;
if(curk >= k)x += (e[i].x-lq)*pag;
ans[e[i].id] += (total-x);
pq = x; lq = e[i].x;
}
}
int resp = 0;
for(int i = 0; i < curi; i++)resp = max(resp, total-ans[i]);
cout<<resp<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
