oj.uz

Submission #599529

# Submission time Handle Problem Language Result Execution time Memory
599529 2022-07-19T15:13:17 Z Pety Autobahn (COI21_autobahn) C++14
50 / 100
 298 ms 24296 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

ll n, k, x;

map<ll, pair<ll, ll>>mp;
struct llervals {
  ll l, r, cost;
  bool operator < (const llervals 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 (ll i = 1; i <= n; i++) {
    ll 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<ll, ll>sum;
  ll last = 0;
  ll 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 (ll i = 1; i <= nr; i++) {
    s[i] = s[i - 1] + 1ll * (v[i].r - v[i].l + 1) * v[i].cost;
  }
  for (ll i = 1; i <= nr; i++) {
    ll idk = i, st = i, dr = nr;
    while (st <= dr) {
      ll 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 (ll i = 1; i <= nr; i++) {
    ll idk = 1, st = 1, dr = i;
    while (st <= dr) {
      ll 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;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 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 212 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 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 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 212 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 0 ms 340 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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 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 212 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 0 ms 340 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 254 ms 24296 KB Output is correct
22 Incorrect 298 ms 24152 KB Output isn't correct
23 Halted 0 ms 0 KB -