Submission #420472

#	Time	Username	Problem	Language	Result	Execution time	Memory
420472		juancarlovieri	Autobahn (COI21_autobahn)	C++17	100 / 100	368 ms	26864 KiB

autobahn

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

#define kath ash
#define int long long

signed main() {
  int n, k, x;
  cin >> n >> k >> x;
  vector<int> l(n), t(n), r(n), events;
  for (int i = 0; i < n; ++i) {
    cin >> l[i] >> t[i] >> r[i];
    events.push_back(l[i]);
    events.push_back(r[i]);
    events.push_back(r[i] + 1);
    events.push_back(r[i] - x);
    events.push_back((l[i] + t[i] - 1));
    events.push_back(l[i] - x + 1);
    events.push_back((l[i] + t[i] - 1) + 1);
    events.push_back(r[i] - x + 1);
    events.push_back((l[i] + t[i] - 1) - x + 1);
    events.push_back((l[i] + t[i] - 1) - x);
  }
  sort(events.begin(), events.end());
  events.resize(unique(events.begin(), events.end()) - events.begin());
  events.push_back(1000000000000);
  vector<int> bad(events.size()), num(events.size());
  for (int i = 0; i < n; ++i) {
    int j = lower_bound(events.begin(), events.end(), l[i]) - events.begin();
    ++num[j];
    j = lower_bound(events.begin(), events.end(), r[i] + 1) - events.begin();
    --num[j];
  }
  for (int i = 0; i < n; ++i) {
    if (l[i] + t[i] - 1 <= r[i]) {
      int j = lower_bound(events.begin(), events.end(), l[i] + t[i]) - events.begin();
      bad[j]++;
      j = lower_bound(events.begin(), events.end(), r[i] + 1) - events.begin();
      bad[j]--;
    }
  }
  for (int i = 1; i < events.size(); ++i) num[i] += num[i - 1], bad[i] += bad[i - 1];
  int curl = events[0], curr = -1000000000000, val = 0, j = 0, ans = 0;
  int goal = 0;
  for (int i = 0; i + 1 < events.size(); i++) {
    curl = events[i];
    if (curr <= curl) {
      curr = curl;
      val = ((num[i] >= k)) * bad[i];
      j = i + 1;
    } else {
      val -= (events[i] - events[i - 1]) * (bad[i - 1]) * (num[i - 1] >= k);
    }
    while (1) {
      if (events[j] > x + curl - 1) {
        val += (bad[j - 1]) * (num[j - 1] >= k) * (curl + x - 1 - curr);
        curr = curl + x - 1;
        break;
      } else {
        val += (bad[j - 1]) * (num[j - 1] >= k) *  (events[j] - 1 - curr);
        curr = events[j] - 1;
        ++j;
      }
    }

    if (val > ans) {
      ans = val;
      goal = events[i];
    }
  }
  cout << ans << endl;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:42:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = 1; i < events.size(); ++i) num[i] += num[i - 1], bad[i] += bad[i - 1];
      |                   ~~^~~~~~~~~~~~~~~
autobahn.cpp:45:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 0; i + 1 < events.size(); i++) {
      |                   ~~~~~~^~~~~~~~~~~~~~~
autobahn.cpp:44:7: warning: variable 'goal' set but not used [-Wunused-but-set-variable]
   44 |   int goal = 0;
      |       ^~~~

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