Submission #1077022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077022		asdfgrace	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	262 ms	13664 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
 
#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));
 
/*
build 1 or 2 bridges
add to baseline of sum of all distances driven without crossing bridge + n
then only consider people crossing
 
k=1:
minimize the sum of all abs(s[i] - x) + abs(t[i] - x)
one of the given locs is optimal
so here treat all s[i] and t[i] the same, sort, etc.

k=2:
starts > lb and ends < rb:
lb + rb <= x + y --> use x
else --> use y
that actually applies to everything
so you can already just sort by sum
and binary search the right bound
given the left bound
but how do you compare between left bounds

okok the hint is you just sort by sum
just iterate over the n or smth breakpoints & look for the min with 2p or smth...
HINT: the median is always optimal
*/
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int k, n;
  cin >> k >> n;
  vector<array<int, 2>> a;
  long long bsl = 0;
  for (int i = 0; i < n; i++) {
    char c1, c2; int i1, i2;
    cin >> c1 >> i1 >> c2 >> i2;
    if (c1 == c2) {
      bsl += abs(i2 - i1);
    } else {
      if (i2 < i1) swap(i1, i2);
      a.push_back({i1, i2});
      bsl++;
    }
  }
  n = (int) a.size();
  if (n == 0) {
    cout << bsl << '\n';
    return 0;
  }
  vector<int> b;
  for (int i = 0; i < n; i++) {
    b.push_back(a[i][0]); b.push_back(a[i][1]);
  }
  sort(b.begin(), b.end());
  if (k == 1) {
    long long sum = 0;
    for (int i = 0; i < 2 * n; i++) {
      sum += b[i] - b[0];
    }
    long long best = sum;
    for (int i = 1; i < 2 * n; i++) {
      sum += (long long) i * (b[i] - b[i - 1]);
      sum -= (long long) (2 * n - i) * (b[i] - b[i - 1]);
      best = min(best, sum);
    }
    cout << best + bsl << '\n'; 
  } else {
    sort(a.begin(), a.end(), [&] (array<int, 2> a1, array<int, 2> a2) {
      return a1[0] + a1[1] < a2[0] + a2[1];
    });
    vector<vector<multiset<int>>> s(2, vector<multiset<int>>(2));
    vector<vector<long long>> sum(2, vector<long long>(2, 0));
    function<void(int, int)> ins = [&] (int i, int x) {
      if (s[i][0].empty() || x <= *s[i][0].rbegin()) {
        s[i][0].insert(x);
        sum[i][0] += x;
        if (s[i][0].size() > s[i][1].size() + 1) {
          int mx = *s[i][0].rbegin();
          s[i][0].erase(s[i][0].find(mx));
          sum[i][0] -= mx;
          s[i][1].insert(mx);
          sum[i][1] += mx;
        }
      } else {
        s[i][1].insert(x);
        sum[i][1] += x;
        if (s[i][1].size() > s[i][0].size()) {
          int mn = *s[i][1].begin();
          s[i][1].erase(s[i][1].find(mn));
          sum[i][1] -= mn;
          s[i][0].insert(mn);
          sum[i][0] += mn;
        }
      }
      
    };
    function<void(int, int)> del = [&] (int i, int x) {
      if (x <= *s[i][0].rbegin()) {
        s[i][0].erase(s[i][0].find(x));
        sum[i][0] -= x;
        if (s[i][1].size() > s[i][0].size()) {
          int mn = *s[i][1].begin();
          s[i][1].erase(s[i][1].find(mn));
          sum[i][1] -= mn;
          s[i][0].insert(mn);
          sum[i][0] += mn;
        }
      } else {
        s[i][1].erase(s[i][1].find(x));
        sum[i][1] -= x;
        if (s[i][0].size() > s[i][1].size() + 1) {
          int mx = *s[i][0].rbegin();
          s[i][0].erase(s[i][0].find(mx));
          sum[i][0] -= mx;
          s[i][1].insert(mx);
          sum[i][1] += mx;
        }
      }
    };
    function<long long(int)> cost = [&] (int i) {
      if (s[i][0].empty()) return 0ll;
      long long med = *s[i][0].rbegin();
      return (med * (long long) s[i][0].size() - sum[i][0])
        + (sum[i][1] - med * (long long) s[i][1].size());
    };
    for (int i = 0; i < n; i++) {
      ins(1, a[i][0]);
      ins(1, a[i][1]);
    }
    long long best = cost(1);
    for (int i = 0; i < n - 1; i++) {
      del(1, a[i][0]);
      del(1, a[i][1]);
      ins(0, a[i][0]);
      ins(0, a[i][1]);
      best = min(best, cost(0) + cost(1));
    }
    cout << best + bsl << '\n';
  }
}
 
/*
any observations help
 
check every line
IF YOUR LINES AREN'T WRONG
CHECK IF YOUR LINES ARE IN THE RIGHT ORDER
 
NEVER GIVE UP
*/

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