Submission #420401

#	Time	Username	Problem	Language	Result	Execution time	Memory
420401		rama_pang	Autobahn (COI21_autobahn)	C++17	100 / 100	358 ms	33528 KiB

autobahn

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, K, X;
  cin >> N >> K >> X;

  vector<int> L(N), T(N), R(N);
  map<int, pair<int, int>> events;
  for (int i = 0; i < N; i++) {
    cin >> L[i] >> T[i] >> R[i];
    events[L[i]].first += 1;
    events[R[i] + 1].first -= 1;
    if (L[i] + T[i] <= R[i]) {
      events[L[i] + T[i]].second += 1;
      events[R[i] + 1].second -= 1;
    }
  }

  int sumBad = 0;
  int sumStay = 0;
  int last = 0;

  vector<array<int, 3>> inter;
  for (auto [t, ev] : events) {
    if (sumStay >= K) {
      inter.push_back({last, t - 1, sumBad});
    }
    last = t;
    sumStay += ev.first;
    sumBad += ev.second;
  }

  // Find length K with maximum inter score
  vector<int> coords;
  for (auto x : inter) {
    coords.emplace_back(x[0] - 1);
    coords.emplace_back(x[0] + X - 1);
    coords.emplace_back(x[1] - X);
    coords.emplace_back(x[1]);
  }
  sort(begin(coords), end(coords));
  coords.resize(unique(begin(coords), end(coords)) - begin(coords));
  vector<long long> coordAns(coords.size());

  int ptr = 0;
  long long overlap = 0;
  for (int cid = 0; cid < int(coords.size()); cid++) {
    while (ptr < int(inter.size()) && inter[ptr][1] < coords[cid]) {
      overlap += 1ll * (inter[ptr][1] - inter[ptr][0] + 1) * inter[ptr][2];
      ptr += 1;
    }
    coordAns[cid] = overlap;
    if (ptr < int(inter.size()) && inter[ptr][0] <= coords[cid]) {
      coordAns[cid] += 1ll * (coords[cid] - inter[ptr][0] + 1) * inter[ptr][2];
    }
  }

  long long ans = 0;
  for (auto x : inter) {
    {
      int it1 = lower_bound(begin(coords), end(coords), x[0] - 1) - begin(coords);
      int it2 = lower_bound(begin(coords), end(coords), x[0] + X - 1) - begin(coords);
      ans = max(ans, coordAns[it2] - coordAns[it1]);
    }
    {
      int it1 = lower_bound(begin(coords), end(coords), x[1] - X) - begin(coords);
      int it2 = lower_bound(begin(coords), end(coords), x[1]) - begin(coords);
      ans = max(ans, coordAns[it2] - coordAns[it1]);
    }
  }

  cout << ans << '\n';
  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50