#include <bits/stdc++.h>
//#include<ext/rope>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC target("avx2")
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define F first
#define S second
#define pb push_back
#define sz(x) int(x.size())
#define el '\n'
#define all(x) x.begin(), x.end()
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;
//typedef tree <ll, null_type, less <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 5e5 + 500;
int pf[N];
ll cnt[N];
int pf1[N];
int l, r, t, n, k, x;
vector <int> v;
vector <pair <int, int> > seg, ex;
int main()
{
// cerr.precision(7);
// cerr << fixed;
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("23.in");
// in("input.txt");
// out("output.txt");
// clock_t start = clock();
cin >> n >> k >> x;
for (int i = 1; i <= n; i++) {
cin >> l >> t >> r;
v.pb(l); v.pb(r); v.pb(r + 1);
seg.pb({l, r});
if (l + t <= r) {
v.pb(l + t);
ex.pb({l + t, r});
}
}
map <int, int> mp;
v.pb(2e9);
sort(all(v));
v.resize(unique(all(v)) - v.begin());
for (int i = 0; i < sz(v); i++) {
mp[v[i]] = i + 1;
}
for (int i = 0; i < sz(seg); i++) {
pf[mp[seg[i].F]]++;
pf[mp[seg[i].S + 1]]--;
}
for (int i = 1; i <= sz(v); i++) {
pf[i] += pf[i - 1];
if (i != sz(v)) {
// cout << "[" << v[i - 1] << ", " << v[i] << ")" << " = " << pf[i] << el;
}
}
for (int i = 0; i < sz(ex); i++) {
pf1[mp[ex[i].F]]++;
pf1[mp[ex[i].S + 1]]--;
}
for (int i = 1; i <= sz(v); i++) {
pf1[i] += pf1[i - 1];
if (i != sz(v)) {
// cout << "[" << v[i - 1] << ", " << v[i] << ")" << " = " << pf1[i] << el;
}
}
for (int i = 1; i <= sz(v); i++) {
cnt[i] += cnt[i - 1];
if (i < sz(v) && pf[i] >= k) {
cnt[i] += pf1[i] * (v[i] - v[i - 1]);
}
}
ll ans = 0;
for (int i = 0, j = 0; i < sz(v); i++) {
while (j < sz(v) && v[j] - v[i] < x) {
j++;
}
// cerr << v[i] << " " << v[j - 1] << el;
ll cur = cnt[j] - cnt[i];
if (pf[j] >= k) {
cur -= pf1[j] * (v[j] - (v[i] + x - 1));
}
ans = max(ans, cur);
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
