Submission #636889

#	Time	Username	Problem	Language	Result	Execution time	Memory
636889		SharpEdged	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	106 ms	11356 KiB

bridge

#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define LSB(x) ((x) & -(x))
#define sz(x) ((int)x.size())

using namespace std;

typedef long long ll;

const char nl = '\n';

struct OrderedSet{
	multiset<ll> lo, hi;
	ll cost = 0;
	ll m;
	OrderedSet() {}
	void Insert(ll x){
		m = (sz(lo) > 0) ? *lo.rbegin() : x;
		cost += abs(x - m);
		if (x <= m) lo.insert(x);
		else hi.insert(x);
		Balance();
	}
	
	void Erase(ll x){
		m = *lo.rbegin();
		cost -= abs(x - m);
		if (x <= m) lo.erase(lo.find(x));
		else hi.erase(hi.find(x));
		Balance();
	}
	
	void Balance(){
		ll l = sz(lo)-1, r = sz(hi), new_m = m;
		if (sz(hi) > sz(lo)){
			ll val = *hi.begin();
			hi.erase(hi.begin());
			lo.insert(val);
			new_m = *lo.rbegin();
			cost += (new_m - m) * (l + 1 - r);
		}
		else if (sz(hi) < sz(lo) - 1){
			ll val = *lo.rbegin();
			lo.erase(lo.find(val));
			hi.insert(val);
			new_m = *lo.rbegin();
			cost += (m - new_m) * (r + 1 - l);
		}
		m = new_m;
	}
};

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int k, n; cin >> k >> n;
	ll base = 0;
	vector<pair<ll, ll>> v;
	for (int i = 0; i < n; i++){
		char z1, z2; ll p1, p2;
		cin >> z1 >> p1 >> z2 >> p2;
		if (z1 == z2) base += abs(p1 - p2);
		else {
			if (p1 > p2) swap(p1, p2);
			v.eb(p1, p2);
			base++;
		}
	}
	sort(all(v));
	OrderedSet sL, sR;
	for (int i = 0; i < sz(v); i++){
		sR.Insert(v[i].f);
		sR.Insert(v[i].s);
	}
	ll ans = sR.cost;
	if (k == 1) { cout << base + ans << nl; return 0; }
	for (int i = 0; i < sz(v); i++){
		sR.Erase(v[i].f);
		sR.Erase(v[i].s);
		sL.Insert(v[i].f);
		sL.Insert(v[i].s);
		ans = min(ans, sL.cost + sR.cost);
	}
	cout << base + ans << nl;
	return 0;
}

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