Submission #617295

#	Time	Username	Problem	Language	Result	Execution time	Memory
617295		EthanKim8683	Palembang Bridges (APIO15_bridge)	C++17	78 / 100	353 ms	15172 KiB

bridge

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

using I = int;
using C = char;
using B = bool;
using Lli = long long int;

vector<pair<I, I>> pais;
vector<I> pois;
vector<pair<I, pair<I, I>>> mids; 
multiset<I> low_lows;
multiset<I> low_upps;
multiset<I> upp_lows;
multiset<I> upp_upps;
Lli dis = 0;

Lli slv1() {
  for (const auto [s, t] : pais) {
    pois.push_back(s);
    pois.push_back(t);
  }
  const I mid = pois.size() / 2;
  nth_element(pois.begin(), pois.begin() + mid, pois.end());
  const I med = pois[mid];
  Lli res = 0;
  for (const auto poi : pois)
    res += abs(med - poi);
  return res;
}

void upp_bal() {
  if (upp_lows.empty() && !upp_upps.empty()) {
    const I mov = *upp_upps.begin();
    upp_lows.insert(mov);
    upp_upps.erase(upp_upps.find(mov));
    return;
  }
  if (upp_upps.size() > upp_lows.size()) {
    const I las = *upp_lows.rbegin();
    const I mov = *upp_upps.begin();
    upp_lows.insert(mov);
    upp_upps.erase(upp_upps.find(mov));
    const I cur = *upp_lows.rbegin();
    dis += (upp_lows.size() - upp_upps.size() - 2) * (cur - las);
  }
  if (upp_lows.size() > upp_upps.size() + 1) {
    const I las = *upp_lows.rbegin();
    const I mov = *upp_lows.rbegin();
    upp_upps.insert(mov);
    upp_lows.erase(upp_lows.find(mov));
    const I cur = *upp_lows.rbegin();
    dis -= (upp_upps.size() - upp_lows.size()) * (las - cur);
  }
}

void low_bal() {
  if (low_upps.size() > low_lows.size()) {
    const I las = *low_lows.rbegin();
    const I mov = *low_upps.begin();
    low_lows.insert(mov);
    low_upps.erase(low_upps.find(mov));
    const I cur = *low_lows.rbegin();
    dis += (low_lows.size() - low_upps.size() - 2) * (cur - las);
  }
  if (low_lows.size() > low_upps.size() + 1) {
    const I las = *low_lows.rbegin();
    const I mov = *low_lows.rbegin();
    low_upps.insert(mov);
    low_lows.erase(low_lows.find(mov));
    const I cur = *low_lows.rbegin();
    dis -= (low_upps.size() - low_lows.size()) * (las - cur);
  }
}

void upp_add(I val) {
  if (upp_lows.empty()) {
    upp_lows.insert(val);
    return;
  }
  const I med = *upp_lows.rbegin();
  if (val > med) {
    upp_upps.insert(val);
    dis += val - med;
  } else {
    upp_lows.insert(val);
    dis += med - val;
  }
  upp_bal();
}

void low_add(I val) {
  if (low_lows.empty()) {
    low_lows.insert(val);
    return;
  }
  const I med = *low_lows.rbegin();
  if (val > med) {
    low_upps.insert(val);
    dis += val - med;
  } else {
    low_lows.insert(val);
    dis += med - val;
  }
  low_bal();
}

void upp_rem(I val) {
  const I med = *upp_lows.rbegin();
  if (val > med) {
    upp_upps.erase(upp_upps.find(val));
    dis -= val - med;
  } else {
    upp_lows.erase(upp_lows.find(val));
    dis -= med - val;
  }
  upp_bal();
}

Lli slv2() {
  for (const auto [s, t] : pais) {
    upp_add(s);
    upp_add(t);
  }
  for (const auto [s, t] : pais)
    mids.push_back({s + (t - s) / 2, {s, t}});
  sort(mids.begin(), mids.end());
  Lli res = dis;
  for (const auto [mid, pai] : mids) {
    const auto [s, t] = pai;
    upp_rem(s);
    upp_rem(t);
    low_add(s);
    low_add(t);
    res = min(res, dis);
  }
  return res;
}

I main(void) {
  cin.tie(0)->sync_with_stdio(0);
  I k, n;
  cin >> k >> n;
  Lli res = 0;
  for (I i = 0; i < n; i++) {
    C p, q;
    I s, t;
    cin >> p >> s >> q >> t;
    if (s > t)
      swap(s, t);
    if (p != q) {
      pais.push_back({s, t});
      res++;
    } else
      res += t - s;
  }
  if (k == 1)
    res += slv1();
  else
    res += slv2();
  printf("%lli\n", res);
  return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37