Submission #249749

#	Time	Username	Problem	Language	Result	Execution time	Memory
249749		AMO5	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	289 ms	12908 KiB

bridge

#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007
 
typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;
 
const int mxn = 1e5+5;
bool DEBUG=0;
ll pref[mxn],suff[mxn];
bool cmp(const pll &a, const pll &b){
	if(a.fi+a.se!=b.fi+b.se)return a.fi+a.se<b.fi+b.se;
	else return a.fi<b.fi;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
	ll k,n;
	vll coor;
	vector<pll>str;
	cin >> k >> n;
	ll ans = 0ll;
	for(int i=0; i<n; i++){
		char p,q; ll s,t;
		cin >> p >> s >> q >> t;
		if(p==q){
			ans += abs(s-t);
		}else{
			if(s>t)swap(s,t);
			ans+=1ll;
			str.eb(s,t);
		}
	}
	n=sz(str);
	if(n==0){
		//no bridge is needed
		cout << ans << endl;
		return 0;
	}
	if(k==1){
		//k=1
		for(ii x:str){
			coor.eb(x.fi);
			coor.eb(x.se);
		}
		sort(all(coor));
		ll bridge1=coor[n-1],bridge2=coor[n]; //bridge 2 is unnecessarily as long as bridge is median 
		ll res1=0ll,res2=0ll;
		for(int i=0; i<n; i++){
			if(bridge1<str[i].fi){
				res1 += 2ll*(str[i].fi-bridge1);
			}else if(bridge1>str[i].se){
				res1 += 2ll*(bridge1-str[i].se);
			}
			if(bridge2<str[i].fi){
				res2 += 2ll*(str[i].fi-bridge2);
			}else if(bridge2>str[i].se){
				res2 += 2ll*(bridge2-str[i].se);
			}
			res1 += str[i].se-str[i].fi;
			res2 += str[i].se-str[i].fi;
		}
		ans += min(res1,res2);
	}else{
		//k=2 
		sort(all(str),cmp);
		multiset<ll>sm,bg;
		ll sum_sm=0ll,sum_bg=0ll;
		for(int i=0; i<n-1; i++){ //bridge 1, pref
			sm.insert(str[i].fi);
			bg.insert(str[i].se);
			sum_sm += str[i].fi;
			sum_bg += str[i].se;
			while(*sm.rbegin()>*bg.begin()){ // swap em, so the median is still at sm(last),bg(first)
				ll dif = *sm.rbegin()-*bg.begin();
				sum_sm -= dif;
				sum_bg += dif;
				sm.insert(*bg.begin());
				bg.insert(*sm.rbegin());
				sm.erase(--sm.end());
				bg.erase(bg.begin());
			}
			pref[i] = sum_bg-sum_sm;
		}
		sm=bg=multiset<ll>();
		sum_sm=sum_bg=0ll;
		for(int i=n-1; i>0; i--){ //bridge 2, suff
			sm.insert(str[i].fi);
			bg.insert(str[i].se);
			sum_sm += str[i].fi;
			sum_bg += str[i].se;
			while(*sm.rbegin()>*bg.begin()){ // swap em
				ll dif = *sm.rbegin()-*bg.begin();
				sum_sm -= dif;
				sum_bg += dif;
				sm.insert(*bg.begin());
				bg.insert(*sm.rbegin());
				sm.erase(--sm.end());
				bg.erase(bg.begin());
			}
			//always throw to bg group, so easier to calc the dif between groups
			suff[i] = sum_bg-sum_sm;
		}
		// combining pref_i+suff_(i+1) as pref and suff go to bridge 1 and 2 respectively
		ll res = 1e18;
		for(int i=0; i<n-1; i++){
			res = min(res,pref[i]+suff[i+1]);
		}
		ans += res;
	}
	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