#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;
const ll inf = 1e9 + 10;
int K;
class sparse_seg{
public:
int create(){
sum.push_back(0);
qtd.push_back(0);
tam.push_back(0);
l.push_back(0);
r.push_back(0);
lazy_qtd.push_back(0);
lazy_sum.push_back(0);
lazy_tam.push_back(0);
return (int)sum.size() - 1;
}
int left( int pos ){
if( l[pos] == 0 ){ int aux = create(); l[pos] = aux; }
return l[pos];
}
int right( int pos ){
if( r[pos] == 0 ){ int aux = create(); r[pos] = aux; }
return r[pos];
}
void refresh( int pos, int ini, int fim ){
if( lazy_qtd[pos] == 0 && lazy_sum[pos] == 0 && lazy_tam[pos] == 0 ) return;
ll aux1 = lazy_qtd[pos]; lazy_qtd[pos] = 0;
ll aux2 = lazy_sum[pos]; lazy_sum[pos] = 0;
ll aux3 = lazy_tam[pos]; lazy_tam[pos] = 0;
qtd[pos] += aux1;
if( aux3 ) tam[pos] = 1LL*(fim - ini + 1)*aux3;
if( aux2 ){
// cout << ini << " " << fim << endl;
// bug(tam[pos]);
}
sum[pos] += tam[pos]*aux2;
if( ini == fim ) return;
left(pos); right(pos);
lazy_qtd[l[pos]] += aux1;
lazy_qtd[r[pos]] += aux1;
lazy_sum[l[pos]] += aux2;
lazy_sum[r[pos]] += aux2;
lazy_tam[l[pos]] = aux3;
lazy_tam[r[pos]] = aux3;
}
void merge( int pos ){
sum[pos] = sum[left(pos)] + sum[right(pos)];
qtd[pos] = qtd[left(pos)] + qtd[right(pos)];
}
void update( int pos, int ini, int fim, int ki, int kf, int t ){
refresh( pos, ini, fim );
if( ki > fim || ini > kf ) return;
if( ki <= ini && fim <= kf ){
if( t == 1 ) lazy_qtd[pos]++;
else lazy_sum[pos]++;
refresh(pos, ini, fim);
return;
}
int mid = (ini + fim)/2;
update( left(pos), ini, mid, ki, kf, t);
update( right(pos), mid + 1, fim, ki, kf, t );
merge( pos );
// if( t == 2 ) cout << ini << " " << fim << endl;
// if( t == 2 ) bug(sum[pos]);
}
void traverse( int pos, int ini, int fim ){
refresh( pos, ini, fim );
if( l[pos] == 0 && r[pos] == 0 ){
if( qtd[pos] >= K ) lazy_tam[pos] = 1;
refresh( pos, ini, fim );
return;
}
int mid = (ini + fim)/2;
traverse( l[pos], ini, mid ); traverse( r[pos], mid + 1, fim );
tam[pos] = tam[l[pos]] + tam[r[pos]];
// cout << ini << " " << fim << endl;
// bug(tam[pos]);
}
ll query( int pos, int ini, int fim, int ki, int kf ){
refresh( pos, ini, fim );
if( ki > fim || ini > kf ) return 0;
if( ki <= ini && fim <= kf ){ return sum[pos];}
int mid = (ini + fim)/2;
return query( left(pos), ini, mid, ki, kf ) + query( right(pos), mid + 1, fim, ki, kf );
}
sparse_seg(){ create(); create(); }
private:
vector<ll> sum, qtd, tam, lazy_qtd, lazy_sum, lazy_tam;
vector<int> l, r;
} seg;
int main(){
ll n, k, x; cin >> n >> k >> x;
K = k;
vector<int> l(n + 1), t(n + 1), r(n + 1);
for( int i = 1; i <= n; i++ ){
cin >> l[i] >> t[i] >> r[i];
// bug(i);
seg.update( 1, 1, inf, l[i], r[i], 1 );
}
seg.traverse( 1, 1, inf );
for( int i = 1; i <= n; i++ ){
// bug(i);
// bug(l[i] + t[i]);
// bug(r[i]);
seg.update( 1, 1, inf, l[i] + t[i], r[i], 2 );
}
ll resp = 0;
for( int i = 1; i <= n; i++ ){
resp = max( resp, seg.query( 1, 1, inf, l[i], min( l[i] + x - 1, inf ) ) );
resp = max( resp, seg.query( 1, 1, inf, t[i], min( t[i] + x - 1, inf ) ) );
resp = max( resp, seg.query( 1, 1, inf, r[i], min( r[i] + x - 1, inf ) ) );
resp = max( resp, seg.query( 1, 1, inf, max( 1LL, l[i] - x), l[i] - 1 ) );
resp = max( resp, seg.query( 1, 1, inf, max( 1LL, t[i] - x), t[i] - 1 ) );
resp = max( resp, seg.query( 1, 1, inf, max( 1LL, r[i] - x), r[i] - 1 ) );
}
cout << resp << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
