제출 #599569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599569		Pety	Autobahn (COI21_autobahn)	C++14	100 / 100	254 ms	27048 KiB

autobahn

#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[400002];
long long s[400002];

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].r - 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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50