#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e6 + 10;
int T[N];
int L[N];
int R[N];
vector<int> imp;
vector<pii> segm;
int cnt[N];
int ban[N];
struct Node{
ll val;
int cnt;
ll lzy;
};
Node TR[N * 4 + 512];
void push(int node, int cl, int cr){
TR[node].val += TR[node].lzy * 1ll * (segm[cr].se - segm[cl].fi + 1);
TR[node].cnt += TR[node].lzy;
if(cl != cr){
TR[node * 2].lzy += TR[node].lzy;
TR[node * 2 + 1].lzy += TR[node].lzy;
}
TR[node].lzy = 0;
}
void upd(int node, int cl, int cr, int tl, int tr, int v){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
TR[node].lzy = v;
push(node, cl, cr);
return;
}
int mid =(cl + cr) / 2;
upd(node * 2, cl, mid, tl, tr, v);
upd(node * 2 + 1, mid + 1, cr, tl, tr, v);
TR[node].val = TR[node * 2].val + TR[node * 2 + 1].val;
}
int getcnt(int node, int cl, int cr, int iq){
push(node, cl, cr);
if(cl == cr)
return TR[node].cnt;
int mid = (cl + cr) / 2;
if(mid >= iq)
return getcnt(node * 2, cl, mid, iq);
else
return getcnt(node * 2 + 1, mid + 1, cr, iq);
}
ll get(int node, int cl, int cr, int tl, int tr){
push(node, cl, cr);
if(cr < tl || cl > tr) return 0ll;
if(cl >= tl && cr <= tr){
return TR[node].val;
}
int mid = (cl + cr) / 2;
return get(node * 2, cl, mid, tl, tr) + get(node * 2 + 1, mid + 1, cr, tl, tr);
}
const int M = 2010;
bool lef[M];
bool rig[M];
int main(){
fastIO;
int n, k, x;
cin >> n >> k >> x;
for(int i = 1; i <= n; i ++ ){
cin >> L[i] >> T[i] >> R[i];
imp.push_back(L[i]);
imp.push_back(R[i]);
if(L[i] + T[i] <= R[i]){
imp.push_back(L[i] + T[i]);
}
}
sort(imp.begin(), imp.end());
imp.resize(unique(imp.begin(), imp.end()) - imp.begin());
for(int i = 0 ; i < imp.size(); i ++ ){
segm.push_back(mp(imp[i], imp[i]));
if(i + 1 < imp.size()){
if(imp[i] + 1 <= imp[i + 1] - 1)
segm.push_back(mp(imp[i] + 1, imp[i + 1] - 1));
}
}
/*
for(auto x : segm){
lef[x.fi]=true;
rig[x.se]=true;
}
segm.clear();
for(int i = 0 ; i <= 2000; i ++ ){
segm.push_back(mp(i, i));
}
*/
int m = segm.size();
int lf, rf;
for(int i = 1; i <= n; i ++ ){
lf = lower_bound(segm.begin(), segm.end(), mp(L[i], L[i])) - segm.begin();
rf = lower_bound(segm.begin(), segm.end(), mp(R[i], R[i])) - segm.begin();
cnt[lf] ++ ;
cnt[rf + 1] -- ;
if(L[i] + T[i] <= R[i]){
lf = lower_bound(segm.begin(), segm.end(), mp(L[i] + T[i], L[i] + T[i])) - segm.begin();
upd(1, 0, m - 1, lf, rf, +1);
ban[lf] ++ ;
ban[rf + 1] -- ;
}
}
ll res = 0;
for(int i = 1; i < m ; i ++ ){
cnt[i] += cnt[i - 1];
ban[i] += ban[i - 1];
}
for(int i = 0 ; i < m ; i ++ ){
if(cnt[i] < k){
upd(1, 0, m - 1, i, i, -ban[i]);
}
}
int iqx;
int nex;
int las;
ll val;
int cc;
for(int i = 0 ; i < m ; i ++ ){
las = lower_bound(segm.begin(), segm.end(), mp(segm[i].fi + x, -1)) - segm.begin();
las -- ;
val = get(1, 0, m - 1, i, las - 1);
if(las < m){
cc = getcnt(1, 0, m - 1, las);
val += max(0,((segm[i].fi + x - 1) - segm[las].fi + 1)) * 1ll * cc;
}
res = max(res, val);
las = lower_bound(segm.begin(), segm.end(), mp(segm[i].se - x + 1, -1)) - segm.begin();
val = get(1, 0, m - 1, las, i);
if(las > 0){
cc = getcnt(1, 0, m - 1, las - 1);
val += max(0,(segm[las - 1].se - (segm[i].se - x + 1) + 1)) * 1ll * cc;
}
res = max(res, val);
}
cout << res << "\n";
return 0;
}
Compilation message
autobahn.cpp: In function 'int main()':
autobahn.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0 ; i < imp.size(); i ++ ){
| ~~^~~~~~~~~~~~
autobahn.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if(i + 1 < imp.size()){
| ~~~~~~^~~~~~~~~~~~
autobahn.cpp:138:9: warning: unused variable 'iqx' [-Wunused-variable]
138 | int iqx;
| ^~~
autobahn.cpp:139:9: warning: unused variable 'nex' [-Wunused-variable]
139 | int nex;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
