Submission #1130774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130774		Hamed_Ghaffari	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	275 ms	11572 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

#define X first
#define Y second
#define SZ(x) ll(x.size())
#define pb push_back
#define Mp make_pair
#define all(x) x.begin(), x.end()

using ll = long long;
using pii = pair<int, int>;

const int  INF = 1e9;

struct sum_set {
  multiset<int> st;
  ll sum=0;
  void insert(int x) {
    st.insert(x);
    sum += x;
  }
  void erase(int x) {
    st.erase(st.find(x));
    sum -= x;
  }
};

struct ds {
  sum_set L, R;
  void fix() {
    while(SZ(R.st)>SZ(L.st)) {
      int x = *R.st.begin();
      L.insert(x);
      R.erase(x);
    }
    while(SZ(R.st)+1<=SZ(L.st)-1) {
      int x = *L.st.rbegin();
      L.erase(x);
      R.insert(x);
    }
  }
  void insert(int x) {
    if(SZ(L.st) && x<=*L.st.rbegin()) L.insert(x);
    else R.insert(x);
    fix();
  }
  void erase(int x) {
    if(SZ(L.st) && x<=*L.st.rbegin()) L.erase(x);
    else R.erase(x);
    fix();
  }
  ll calc() {
    if(L.st.empty()) return 0;
    return SZ(L.st)*(*L.st.rbegin()) - L.sum + R.sum - SZ(R.st)*(*L.st.rbegin());
  }
} L, R;

const int MXN = 1e5+5;
int S[MXN], T[MXN];
ll ans, pre;
char P[MXN], Q[MXN];
int k, n;

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> k >> n;
  vector<pii> vc;
  for(int i=0; i<n; i++) {
    cin >> P[i] >> S[i] >> Q[i] >> T[i];
    if(P[i]==Q[i]) pre += abs(S[i]-T[i]);
    else pre++, vc.pb(Mp(S[i], T[i]));
  }
  for(auto [s, t] : vc) R.insert(s), R.insert(t);
  ans = pre+R.calc();
  if(k==1) {
    cout << ans << '\n';
    return 0;
  }
  sort(all(vc), [&](pii x, pii y) {
    return x.X+x.Y<y.X+y.Y;
  });
  for(auto [s, t] : vc) {
    L.insert(s); L.insert(t);
    R.erase(s); R.erase(t);
    ans = min(ans, pre+L.calc()+R.calc());
  }
  cout << ans << '\n';
  return 0;
}

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