Submission #978118

#	Time	Username	Problem	Language	Result	Execution time	Memory
978118		iag99	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	856 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll =long long;
using pi=pair<int,int>;
bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.first + a.second < b.first + b.second;
}
int k,n;
multiset<int> low,high;
vector<char> zone1(n), zone2(n);
vector<int> home(n), office(n);
ll lsum=0, rsum=0;
void insert(int x)
{
	int median=*low.rbegin();
	if(x<=median)
	{
		low.insert(x);
		lsum+=x;
		if(low.size()>high.size()+1)
		{
			int tomove=*low.rbegin();
			low.erase(low.find(*low.rbegin()));
			high.insert(tomove);
			lsum-=tomove;
			rsum+=tomove;
		}
	}
	else
	{
		high.insert(x);
		rsum+=x;
		if(high.size()>low.size())
		{
			int tomove=*high.begin();
			low.insert(*high.begin());
			high.erase(high.find(*high.begin()));
			lsum+=tomove;
			rsum-=tomove;
		}
	}
}
ll pref[100001];
int main() 
{
	//freopen("hayfeast.in", "r", stdin);
	// the following line creates/overwrites the output file
	//freopen("hayfeast.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll same_side = 0;
	vector<pair<int, int>> v = {{0, 0}};
	cin>>k>>n;
	/*
	 * k=bridges
	 * n=people
	*/

	/*
	 If home and office are in the same zone, the distance is simply abs(office[i]-home[i])
	 * Otherwise, try to split the prefix of people that will use the first bridge. In both segments the bridge should be in median
	 * Use sliding median to update the median
	 * Keep a sum of elements in low and high in order to calculate the answer efficently
	*/
	for(int i=0; i<n; i++)
	{
		cin>>zone1[i]>>home[i]>>zone2[i]>>office[i];
		if(zone1[i]==zone2[i]) same_side+=abs(home[i]-office[i]);
		else v.push_back({home[i], office[i]});
	}
	sort(v.begin(), v.end(), cmp);
	n=v.size()-1;
	same_side+=n;
	lsum=rsum=0;
	for(int i=1; i<=n; i++)
	{
		insert(v[i].first);
		insert(v[i].second);
		pref[i]=rsum-lsum;
	}
	ll ans=pref[n];
	if(k==2)
	{
		while(low.size()) low.erase(low.begin());
		while(high.size()) high.erase(high.begin());
		lsum = rsum = 0;
		
		for (int i = n; i; i--) {
			insert(v[i].first);
			insert(v[i].second);
			ans = min(ans, rsum - lsum + pref[i - 1]);
		}
	}
	cout << same_side + ans;

	return 0;
}

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