Submission #117555

#	Time	Username	Problem	Language	Result	Execution time	Memory
117555		MAMBA	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	322 ms	23940 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

inline void read() {}
template <class S>
inline void read(S &arg) {
  cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
  while (Lptr != Rptr) {
    read(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
  read(arg);
  read(rest...);
}

inline void write() {}
template <class S>
inline void write(S arg) {
  cout << arg;
}
template <class S>
inline void weiteA(S Lptr, S Rptr) {
  if (Lptr != Rptr) {
    write(*Lptr);
    Lptr++;
  }
  while (Lptr != Rptr) {
    write(' ');
    write(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void write(S arg, T... rest) {
  write(arg);
  write(' ');
  write(rest...);
}

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

template <class T, class S>
inline bool smin(T &a, S b) {
  return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
  return a < (T)b ? a = b, 1 : 0;
}

constexpr int MOD = 998244353;
constexpr int N = 1e6 + 10;

template <typename T>
inline T mod(T &v) {
  return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
  return mod(l += r);
}
ll po(ll v, ll u) {
  return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}

int k, n, cnt;
ll bias, local;
pii p[N];

multiset<int> st[2];
multiset<int>::iterator it;
ll res[N][2];

inline void insert(int b, pii a) {
  st[b].insert(a.first);
  st[b].insert(a.second);
}

inline void f(int id) {
  insert(id, p[0]);
  res[0][id] = p[0].second - p[0].first;
  it = st[id].begin();
  rep(i, 1, cnt) {
    insert(id, p[i]);
    int del = abs(p[i].first - *it) + abs(p[i].second - *it);
    if (p[i].first >= *it) {
      int tmp = *it;
      it++;
      del -= 2 * (*it - tmp);
    } else if (*it > p[i].second)
      it--;
    res[i][id] = res[i - 1][id] + del;
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  read(k, n);
  rep(i, 0, n) {
    char a, b;
    int A, B;
    read(a, A, b, B);
    if (A > B) swap(A, B);
    p[cnt++] = {A, B};
    if (a == b) {
      bias += abs(A - B);
      cnt--;
    }
  }

  bias += cnt;

  sort(p, p + cnt,
       [](pii l, pii r) { return l.first + l.second < r.first + r.second; });

  f(0);
  reverse(p, p + cnt);
  f(1);
  if (k == 1) return write(bias + res[cnt - 1][0]), 0;

  ll best = bias + res[cnt - 1][0];

  rep(i, 1, cnt) smin(best, bias + res[i - 1][0] + res[cnt - i - 1][1]);

  write(best);

  return 0;
}

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