#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ll n, k, x;
map<int, ll> pref, in, out, skok;
map<int, bool> good;
ll ans = -1;
unordered_set< int > se;
int main()
{
ios::sync_with_stdio(0); cin.tie(NULL);
cin >> n >> k >> x;
for(int i = 1; i <= n; i++)
{
int l, t, r;
cin >> l >> t >> r;
se.insert(l);
se.insert(l + t);
se.insert(r);
if (l - x >= 1)
se.insert(l - x);
if (l + t - x >= 1)
se.insert(l + t - x);
if (r - x >= 1)
se.insert(r - x);
in[l]++; out[r]++;
skok[l + t]++;
good[l] = 1; good[l + t] = 1; good[r] = 1;
}
ll cnt = 0, sum = 0, cur = 0, lst = -1;
for(auto i : se)
{
if (cnt >= k && lst != -1) sum += (i - lst - 1)* 1ll * cur;
cnt += in[i];
cur += skok[i];
if (cnt >= k) sum += cur;
//cout << cnt << ' ' << cur << ' ' << i << endl;
cnt -= out[i];
cur -= out[i];
pref[i] = sum;
//ans = max(ans, sum);
lst = i;
}
//for(auto u : pref) cout << u.fi << ' ' << u.sd << endl;
for(auto i : se)
{
if (!good[i]) continue;
if (i - x >= 0)
ans = max(ans, pref[i] - pref[i - x]);
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
