Submission #1194321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194321		Xiaoyang	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	138 ms	12884 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 1ll<<60
#define rep(i,a,b) for (ll i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
#define endl "\n"
void inc(ll &a,ll b) {a=(a+b)%mod;}
void dec(ll &a,ll b) {a=(a-b+mod)%mod;}
int lowbit(ll x) {return x&(-x);}

vector<ll>alist;
ll k,n;
const ll maxn = 1e5+5;
ll pre[maxn],suff[maxn];
ll lsum=0,rsum=0;

multiset<ll>lo,hi;
void maintain(){
	while(SZ(lo)>SZ(hi)+1){
		ll tmp=*(--lo.end());
		hi.insert(*(--lo.end()));
		rsum+=tmp;
		lo.erase(--lo.end());
		lsum-=tmp;
	}
	while(SZ(hi)>SZ(lo)){
		ll tmp=*hi.begin();
		lo.insert(*hi.begin());
		lsum+=tmp;
		hi.erase(hi.begin());
		rsum-=tmp;
	}
}
void add(ll x){
	if(hi.empty() or *hi.begin()>x)lo.insert(x),lsum+=x;
	else hi.insert(x),rsum+=x;
	maintain();
}
void rem(ll x){//remove element
	if(lo.find(x)!=lo.end())lo.erase(lo.find(x)),lsum-=x;
	else if(hi.find(x)!=hi.end())hi.erase(hi.find(x)),rsum-=x;
	maintain();
}
ll med(){// lo contains ceil(n/2),hi contains floor(n/2)
	return *(--lo.end());
}
void reset(){
	lo.clear();
	hi.clear();
	lsum=0;
	rsum=0;
	return;
}

bool cmp(pll a,pll b){//si+ti<sj+tj
	return a.fi+a.se<b.fi+b.se;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	//freopen("i.txt", "r", stdin);
	cin>>k>>n;
	if(k==1){
		vector<ll>s,t,b;
		ll ans=0;
		rep(i,0,n){
			char pp,qq;
			ll ss,tt;
			cin>>pp>>ss>>qq>>tt; 
			if(pp==qq)ans+=abs(tt-ss);
			else{
				ans++;//cross bridge
				b.pb(ss);b.pb(tt);
				s.pb(ss);
				t.pb(tt);
			}
		}
		sort(ALL(b));
		ll mid=0;
		if(SZ(b)>0)mid=b[SZ(b)/2];
		ll dist=0;
		rep(i,0,SZ(s)){
			dist+=abs(mid-s[i])+abs(mid-t[i]);
		}
		cout<<dist+ans;
		return 0;
	}
	ll tmp=0;
	vector<pll>alist;
	rep(i,0,n){
		char pp,qq;
		ll ss,tt;
		cin>>pp>>ss>>qq>>tt; 
		if(pp==qq)tmp+=abs(tt-ss);//no need care about this citizen afterwards alr
		else{
			tmp++;//cross bridge
			alist.pb(MP(ss,tt));
		}
	}
	sort(ALL(alist),cmp);
	n=alist.size();//new n is just all the citizens that have to cross the bridge
	rep(i,0,n){//iterate where the bridges are built to split into 2 groups,will def be on an office/house 
		add(alist[i].fi);
		add(alist[i].se);
		pre[i]=rsum-lsum;
	}
	reset();
	for(int i=n-1;i>0;i--){
		add(alist[i].fi);
		add(alist[i].se);
		suff[i]=rsum-lsum;
	}
	ll ans=0,mn=inf;
	rep(i,0,n){
		mn=min(mn,pre[i]+suff[i+1]);
	}
	if(mn==inf)ans=tmp;
	else ans=mn+tmp;
	cout<<ans;
	return 0;
}

/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

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