Submission #757822

#	Time	Username	Problem	Language	Result	Execution time	Memory
757822		taher	Autobahn (COI21_autobahn)	C++17	100 / 100	96 ms	9380 KiB

autobahn

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, x;
  cin >> n >> k >> x;
  vector<array<int, 3>> events;
  for (int i = 0; i < n; i++) {
    int l, t, r;
    cin >> l >> t >> r;
    events.push_back({l, +1, 0});
    int s = 0;
    int p = l + t;
    if (p < r + 1) {
      s = 1;
      events.push_back({p, +1, s});
    }
    events.push_back({r + 1, -1, s});
  }
  sort(events.begin(), events.end(), [&](array<int, 3> i, array<int, 3> j) {
    if (i[0] == j[0]) {
      return i[1] < j[1];
    }
    return i[0] < j[0];
  });
  vector<array<int, 2>> d;
  auto Update = [&](int p, int add) {
    if (add == 0) {
      return ;
    }
    if ((int) d.size() > 0 && d.back()[0] == p) {
      d[(int) d.size() - 1][1] += add;
    } else {
      d.push_back({p, add});
    }
    return ;
  };
  int openGood = 0;
  int openAll = 0;
  for (int i = 0; i < (int) events.size(); i++) {
    int s = events[i][2];
    int v = events[i][1];
    int pos = events[i][0];
    if (v == +1) {
      if (s) {
        openGood += 1;
        if (openAll >= k) {
          Update(pos, +1);
        }
      } else {
        openAll += 1;
        if (openAll == k) {
          Update(pos, +openGood);
        }
      }
    } else {
      if (s) {
        openGood -= 1;
        if (openAll >= k) {
          Update(pos, -1);
        }
      }
      openAll -= 1;
      if (openAll == k - 1) {
        Update(pos, -openGood);
      }
    }
  }

  const int inf = 1000000000;

  int len = (int) d.size();

  vector<long long> prefD(len);
  vector<long long> prefP(len);
  for (int i = 0; i < len; i++) {
    if (i > 0) {
      prefD[i] += prefD[i - 1];
      prefP[i] += prefP[i - 1];
    }
    prefD[i] += d[i][1];
    prefP[i] += 1LL * d[i][0] * d[i][1];
  }

  auto Calc = [&](int ptRight) {
    auto ptr0 = lower_bound(d.begin(), d.end(), array<int, 2> ({ptRight - x, inf})) - d.begin();
    auto ptr1 = lower_bound(d.begin(), d.end(), array<int, 2> ({ptRight, inf})) - d.begin();
    ptr1 -= 1;
    if (ptr1 < 0) return 0LL;
    long long ret = 1LL * (ptRight + 1) * (prefD[ptr1] - (ptr0 > 0 ? prefD[ptr0 - 1] : 0LL)) - (prefP[ptr1] - (ptr0 > 0 ? prefP[ptr0 - 1] : 0LL));
    if (ptr0 > 0) {
      assert(ptRight > x);
      ret += 1LL * prefD[ptr0 - 1] * x;
    }
    return ret;
  };

  long long res = 0;

  for (int i = 0; i < (int) d.size(); i++) {
    int pos = d[i][0];
    int c = d[i][1];
    if (c < 0) {
      res = max(res, Calc(pos - 1));
    }
  }

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

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