#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vLL>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;
ll n, k, x;
map<int, ll> pref, in, out, skok;
map<int, bool> good;
ll ans = -1;
vi vec;
void solve(){
cin >> n >> k >> x;
pref[0] = 0;
for(int i=1; i<=n; i++){
int l, t, r;
cin >> l >> t >> r;
vec.PB(l);
vec.PB(l + t);
vec.PB(r);
if(l - x >= 1) vec.PB(l - x);
if(l + t - x >= 1) vec.PB(l + t - x);
if(r - x >= 1) vec.PB(r - x);
in[l]++;
out[r]++;
skok[l + t]++;
good[l] = 1;
good[l + t] = 1;
good[r] = 1;
}
sort(all(vec));
vec.erase(unique(all(vec)), vec.end());
ll cnt = 0, sum = 0, cur = 0, lst = -1;
for(const auto &i : vec){
if(cnt >= k and lst != -1) sum += (ll)(i - lst - 1) * (ll)cur;
cnt += in[i];
cur += skok[i];
if(cnt >= k) sum += cur;
cnt -= out[i];
cur -= out[i];
pref[i] = sum;
lst = i;
}
for(const auto &i : vec){
if(!good[i]) continue;
if(i - x >= 0) ans = max(ans, pref[i] - pref[i - x]);
}
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
//cin >> t;
while(t--)solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
2 ms |
596 KB |
Output is correct |
| 13 |
Correct |
2 ms |
596 KB |
Output is correct |
| 14 |
Correct |
2 ms |
596 KB |
Output is correct |
| 15 |
Correct |
2 ms |
596 KB |
Output is correct |
| 16 |
Correct |
2 ms |
596 KB |
Output is correct |
| 17 |
Correct |
2 ms |
596 KB |
Output is correct |
| 18 |
Correct |
2 ms |
596 KB |
Output is correct |
| 19 |
Correct |
2 ms |
596 KB |
Output is correct |
| 20 |
Correct |
2 ms |
596 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
2 ms |
596 KB |
Output is correct |
| 13 |
Correct |
2 ms |
596 KB |
Output is correct |
| 14 |
Correct |
2 ms |
596 KB |
Output is correct |
| 15 |
Correct |
2 ms |
596 KB |
Output is correct |
| 16 |
Correct |
2 ms |
596 KB |
Output is correct |
| 17 |
Correct |
2 ms |
596 KB |
Output is correct |
| 18 |
Correct |
2 ms |
596 KB |
Output is correct |
| 19 |
Correct |
2 ms |
596 KB |
Output is correct |
| 20 |
Correct |
2 ms |
596 KB |
Output is correct |
| 21 |
Execution timed out |
1097 ms |
171700 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
