| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 599527 |
2022-07-19T15:12:45 Z |
Pety |
Autobahn (COI21_autobahn) |
C++14 |
|
278 ms |
25028 KB |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 1e9;
const int MOD = 1e9 + 7;
int n, k, x;
map<int, pair<int, int>>mp;
struct intervals {
int l, r, cost;
bool operator < (const intervals other) {
return l < other.l;
}
} v[300002];
long long s[300002];
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k >> x;
for (int i = 1; i <= n; i++) {
int a, b,c;
cin >> a >> b >> c;
if (a + b - 1 < c) {
mp[a + b].second++;
mp[c + 1].second--;
}
mp[a].first++;
mp[c + 1].first--;
}
pair<int, int>sum;
int last = 0;
int nr = 0;
for (auto it2 : mp) {
if (sum.first >= k && sum.second) {
v[++nr] = {last, it2.first-1, sum.second};
}
auto it = it2.second;
sum.first += it.first;
sum.second += it.second;
last = it2.first;
}
sort(v + 1,v + nr + 1);
ll ans = 0;
for (int i = 1; i <= nr; i++) {
s[i] = s[i - 1] + 1ll * (v[i].r - v[i].l + 1) * v[i].cost;
}
for (int i = 1; i <= nr; i++) {
int idk = i, st = i, dr = nr;
while (st <= dr) {
int mij = (st + dr) / 2;
if (v[mij].l <= v[i].l + x - 1) {
idk = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
ll val = s[idk] - s[i - 1];
if (v[i].l + x - 1 <= v[idk].r)
val -= 1ll * (v[idk].r - v[i].l - x + 1) * v[idk].cost;
ans = max(ans, val);
}
for (int i = 1; i <= nr; i++) {
int idk = 1, st = 1, dr = i;
while (st <= dr) {
int mij = (st + dr) / 2;
if (v[mij].r >= v[i].l - x + 1) {
idk = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
ll val = s[i] - s[idk - 1];
if (v[i].r - x + 1 >= v[idk].l)
val -= 1ll * (v[i].r - x + 1 - v[idk].l) * v[idk].cost;
ans = max(ans, val);
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
273 ms |
22332 KB |
Output is correct |
| 22 |
Incorrect |
278 ms |
25028 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
