#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
using namespace std;
const int maxn = 3e5 + 5;
struct CTDL{
int l = 0,r = 0,t = 0;
bool operator <(const CTDL&other) const{
if (l < other.l) return 1;
if (l > other.l) return 0;
return (r < other.r);
}
};
bool cmp(pair <int,int> x,pair <int,int> y){
if (x.se < y.se) return 1;
if (x.se > y.se) return 0;
return (x.fi < y.fi);
}
struct DSA{
vector <pair<int,int>> L,R;
vector <ll> SLfi,SLse,SRfi,SRse,preL,preR;
ll sum = 0,sumR = 0;
void prep(){
int N = L.size();
for (int i = 0 ; i < N ; i++){
if (i){
preL[i] = preL[i - 1];
SLfi[i] = SLfi[i - 1];
SLse[i] = SLse[i - 1];
}
preL[i] += L[i].se - L[i].fi + 1;
SLfi[i] += L[i].fi;
SLse[i] += L[i].se;
}
for (int i = 0 ; i < N ; i++){
if (i){
preR[i] = preR[i - 1];
SRfi[i] = SRfi[i - 1];
SRse[i] = SRse[i - 1];
}
preR[i] += R[i].se - R[i].fi + 1;
SRfi[i] += R[i].fi;
SRse[i] += R[i].se;
}
}
void inputarr(const vector <pair<int,int>> &vec){
for (pair <int,int> x : vec){
L.push_back(x);
R.push_back(x);
preL.push_back(0);
preR.push_back(0);
SLfi.push_back(0);
SLse.push_back(0);
SRfi.push_back(0);
SRse.push_back(0);
sum += x.se - x.fi + 1;
}
sort(L.begin(),L.end());
sort(R.begin(),R.end(),cmp);
prep();
}
ll dif(int vt,bool type){
ll res = 0;
int N = L.size();
if (!type){
pair <int,ll> C;
int l = 0,r = R.size() - 1,vt1 = -1;
while (l <= r){
int w = (l + r)/2;
if (R[w].se < vt){
vt1 = w;
l = w + 1;
}
else r = w - 1;
}
l = 0;r = L.size() - 1;int vt2 = N;
while (l <= r){
int w = (l + r)/2;
if (L[w].fi > vt){
vt2 = w;
r = w - 1;
}
else l = w + 1;
}
C.se = SLfi[N - 1];
C.fi = N;
if (vt1 != -1){
C.fi -= vt1 + 1;
C.se -= SRfi[vt1];
}
if (vt2 != N){
C.fi -= (N - vt2);
ll T = 0;
if (vt2 != 0)
T = SLfi[vt2 - 1];
C.se -= (SLfi[N - 1] - T);
}
res = (ll)C.fi*(ll)vt - C.se;
}
else{
pair <int,ll> C;
C.fi = N;
C.se = SLse[N - 1];
int l = 0,r = N - 1,vt1 = -1;
while (l <= r){
int w = (l + r)/2;
if (R[w].se < vt){
vt1 = w;
l = w + 1;
}
else r = w - 1;
}
l = 0;r = N - 1;int vt2 = -1;
while (l <= r){
int w = (l + r)/2;
if (L[w].fi > vt){
vt2 = w;
r = w - 1;
}
else l = w + 1;
}
if (vt1 != -1){
C.fi -= vt1 + 1;
C.se -= SRse[vt1];
}
if (vt2 != -1){
C.fi -= (N - vt2);
ll T = 0;
if (vt2 != 0)
T = SLse[vt2 - 1];
C.se -= SLse[N - 1] - T;
}
res = C.se - (ll)C.fi*(ll)vt;
}
return res;
}
ll outs(int vt,bool type){
ll res = 0;
int N = L.size();
if (!type){
int l = 0,r = N - 1,vt1 = -1;
while (l <= r){
int w = (l + r)/2;
if (R[w].se < vt){
vt1 = w;
l = w + 1;
}
else r = w - 1;
}
if (vt1 != -1)
res = preR[vt1];
}
else{
int l = 0,r = N - 1,vt1 = -1;
while (l <= r){
int w = (l + r)/2;
if (L[w].fi > vt){
vt1 = w;
r = w - 1;
}
else l = w + 1;
}
if (vt1 != -1){
res = preL[N - 1];
if (vt1 != 0)
res -= preL[vt1 - 1];
}
}
return res;
}
ll getval(int l,int r){
ll T = sum;
T -= dif(l,0);
T -= dif(r,1);
T -= outs(l,0);
T -= outs(r,1);
return T;
}
ll calc(int l,int r){
if (!L.size() || l > R.back().se || r < L[0].fi) return 0;
if (l <= L[0].fi && r >= R.back().se) return sum;
l = max(l,L[0].fi);
r = min(r,R.back().se);
return getval(l,r);
}
};
int C[maxn];
ll pre[maxn];
priority_queue <int,vector<int>,greater<int>> pq;
vector <pair<int,int>> ak;
vector <vector<pair<int,int>>> vec(maxn);
DSA lst[maxn];
CTDL a[maxn];
void prepare(int n,int k){
sort(a + 1,a + 1 + n);
for (int i = 1 ; i <= n ; i++){
pq.push(a[i].r);
while (pq.size() > k) pq.pop();
if (pq.size() >= k){
int T = pq.top();
if (T >= a[i].l)
ak.push_back({a[i].l,T});
}
}
sort(ak.begin(),ak.end());
}
void simplify(){
vector <pair<int,int>> tmp;
int p = 0;
while (p < ak.size()){
int P = p;
int lim = ak[p].se;
while (P < ak.size() && ak[P].fi <= lim){
lim = max(lim,ak[P].se);
P++;
}
P--;
tmp.push_back({ak[p].fi,ak[P].se});
p = P + 1;
}
ak = tmp;
sort(ak.begin(),ak.end());
}
void perf(int p,int l,int r){
if (r < ak[p].fi || l > ak[p].se) return;
if (l == ak[p].fi && r == ak[p].se){
C[p]++;
C[p + 1]--;
return;
}
l = max(l,ak[p].fi);
r = min(r,ak[p].se);
vec[p].push_back({l,r});
}
void add_to_arr(int L,int R){
if (R < ak[0].fi || L > ak.back().se) return;
int l = 0,r = ak.size() - 1,d = 0,c = ak.size();
while (l <= r){
int w = (l + r)/2;
if (ak[w].se >= L){
d = w;
r = w - 1;
}
else l = w + 1;
}
l = 0;r = ak.size() - 1;
while (l <= r){
int w = (l + r)/2;
if (ak[w].fi <= R){
c = w;
l = w + 1;
}
else r = w - 1;
}
if (d > c) return;
perf(d,L,R);
if (d != c){
perf(c,L,R);
C[d + 1]++;
C[c]--;
}
}
void genarr(int n,int k){
for (int i = 1 ; i <= n ; i++)
if (a[i].l + a[i].t <= a[i].r)
add_to_arr(a[i].l + a[i].t,a[i].r);
}
void deeppre(int p){
if (!vec[p].size()) return;
lst[p].inputarr(vec[p]);
}
void getpre(){
int N = ak.size() - 1;
pre[0] = (ll)C[0]*(ll)(ak[0].se - ak[0].fi + 1);
deeppre(0);
for (int i = 1 ; i <= N ; i++){
C[i] += C[i - 1];
pre[i] = pre[i - 1] + (ll)C[i]*(ll)(ak[i].se - ak[i].fi + 1);
deeppre(i);
}
}
ll solve(int l,int r){
ll res = 0;
if (l > ak.back().se || r < ak[0].fi) return 0;
int d = 0,c = ak.size() - 1,vt1 = -1;
while (d <= c){
int w = (d + c)/2;
if (ak[w].se >= l){
vt1 = w;
c = w - 1;
}
else d = w + 1;
}
int vt2 = -1;
d = 0;c = ak.size() - 1;
while (d <= c){
int w = (d + c)/2;
if (ak[w].fi <= r){
vt2 = w;
d = w + 1;
}
else c = w - 1;
}
if (vt1 > vt2) return 0;
if (vt1 == vt2) return lst[vt1].calc(l,r);
res = lst[vt1].calc(l,r) + lst[vt2].calc(l,r);
res += pre[vt2 - 1] - pre[vt1];
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k,x;
cin >> n >> k >> x;
for (int i = 1 ; i <= n ; i++)
cin >> a[i].l >> a[i].t >> a[i].r;
prepare(n,k);
if (!ak.size()){
cout << 0;
return 0;
}
simplify();
genarr(n,k);
getpre();
ll res = 0;
for (int i = 1 ; i <= n ; i++){
res = max(res,solve(a[i].l,a[i].l + x - 1));
res = max(res,solve(a[i].l + a[i].t,a[i].l + a[i].t + x - 1));
if (a[i].r >= x)
res = max(res,solve(a[i].r - x + 1,a[i].r));
}
cout << res;
// cout << solve(x);
return 0;
}
Compilation message
autobahn.cpp: In function 'void prepare(int, int)':
autobahn.cpp:235:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
235 | while (pq.size() > k) pq.pop();
| ~~~~~~~~~~^~~
autobahn.cpp:237:17: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
237 | if (pq.size() >= k){
| ~~~~~~~~~~^~~~
autobahn.cpp: In function 'void simplify()':
autobahn.cpp:249:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
249 | while (p < ak.size()){
| ~~^~~~~~~~~~~
autobahn.cpp:253:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
253 | while (P < ak.size() && ak[P].fi <= lim){
| ~~^~~~~~~~~~~
autobahn.cpp: In function 'int main()':
autobahn.cpp:375:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
375 | for (int i = 1 ; i <= n ; i++)
| ^~~
autobahn.cpp:378:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
378 | prepare(n,k);
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
70992 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
73052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
70992 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
73052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
70992 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
73052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
