Submission #331991

#	Time	Username	Problem	Language	Result	Execution time	Memory
331991		tzxydby	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	644 ms	13156 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
struct fhq
{
	multiset<int>s1,s2;
	long long sum1,sum2;
	void bal()
	{
		while(s1.size()>s2.size())
		{
			auto it=(--s1.end());
			s2.insert(*it);
			sum2+=*it;
			sum1-=*it;
			s1.erase(it);
		}
		while(s1.size()<s2.size())
		{
			auto it=s2.begin();
			s1.insert(*it);
			sum1+=*it;
			sum2-=*it;
			s2.erase(it);
		}
	}
	void add(int v)
	{
		s1.insert(v);
		sum1+=v;
		bal();
	}
	void del(int v)
	{
		if(s1.find(v)!=s1.end())
		{
			s1.erase(s1.find(v));
			sum1-=v;
		}
		else
		{
			s2.erase(s2.find(v));
			sum2-=v;
		}
		bal();
	}
	long long sol()
	{
		if(!s2.size())
			return 0;
		long long k=*s2.begin();
		return k*s1.size()-sum1+sum2-k*s2.size();
	}
}t1,t2;
int n,k;
long long tot,ans;
struct node
{
	int l,r;
	bool operator<(const node k)const
	{
		return l+r<k.l+k.r;
	}
};
vector<node>a;
int main()
{
	ios::sync_with_stdio(false);
	cin>>k>>n;
	for(int i=1;i<=n;i++)
	{
		int l,r;
		char p,q;
		cin>>p>>l>>q>>r;
		if(p==q)
			tot+=abs(l-r);
		else
		{
			a.push_back({l,r});
			t2.add(l);
			t2.add(r);
			tot++;
		}
	}
	ans=t1.sol()+t2.sol();
	if(k==1)
	{
		ans+=tot;
		cout<<ans<<endl;
		return 0;
	}
	sort(a.begin(),a.end());
	for(auto i:a)
	{
		int l=i.l,r=i.r;
		t1.add(l);
		t1.add(r);
		t2.del(l);
		t2.del(r);
		ans=min(ans,t1.sol()+t2.sol());
	}
	ans+=tot;
	cout<<ans<<endl;
	return 0;
}

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