Submission #26420

#	Time	Username	Problem	Language	Result	Execution time	Memory
26420		zscoder	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	136 ms	9932 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

bool cmp(const ii &a, const ii &b)
{
	if(a.fi+a.se!=b.fi+b.se) return a.fi+a.se<b.fi+b.se;
	return a.fi<b.fi;
}

priority_queue<ll, vector<ll>, less<ll> > L;
priority_queue<ll, vector<ll>, greater<ll> > R;
ll lsum = 0;
ll rsum = 0;
int siz;
ll dpl[100001];
ll dpr[100001];

void add(ll x, ll y)
{
	R.push(x);
	R.push(y);
	siz++;
	rsum+=(x+y);
	while(R.size()>siz)
	{
		ll tmp = R.top();
		L.push(tmp);
		R.pop();
		lsum+=tmp; rsum-=tmp;
	}
	while(L.top()>R.top())
	{
		ll l = L.top(); ll r = R.top();
		lsum+=r-l; rsum+=l-r;
		L.pop();R.pop();
		L.push(r); R.push(l);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll k, n; cin>>k>>n;
	vector<ii> vec;
	ll ans=0;
	ll anstmp=0;

	for(int i=0;i<n;i++)
	{
		char c1; cin>>c1;
		ll x; cin>>x;
		char c2; cin>>c2;
		ll y; cin>>y;
		if(c1==c2)
		{
			ans+=abs(y-x);
			anstmp+=abs(y-x);
		}
		else
		{
			vec.pb(mp(min(x,y),max(x,y)));
			ans+=max(x,y)-min(x,y)+1;
		}
	}
	n=vec.size();
	if(n==0)
	{
		cout<<ans<<'\n';
		return 0;
	}
	if(k==1)
	{
		vector<ll> coord;
		for(int i=0;i<n;i++)
		{
			coord.pb(vec[i].fi); coord.pb(vec[i].se);
		}
		sort(coord.begin(),coord.end());
		ll bridge = coord[n-1];
		for(int i=0;i<n;i++)
		{
			ll l=vec[i].fi; ll r=vec[i].se;
			if(bridge<l)
			{
				ans+=2LL*(l-bridge);
			}
			else if(bridge>r)
			{
				ans+=2LL*(bridge-r);
			}
		}
		cout<<ans<<'\n';
		return 0;
	}
	ans=anstmp;
	sort(vec.begin(),vec.end(),cmp);
	ll mini=ll(1e18);
	siz=0;
	dpl[0]=0;
	dpr[n]=0;

	for(int i=0;i<n;i++)
	{
		add(vec[i].fi,vec[i].se);
		ll cursum = 0;
		assert(L.size()==R.size());
		assert(L.top()<=R.top());
		cursum += rsum - lsum;
		dpl[i+1] = cursum;
	}

	siz=0;
	lsum=rsum=0;
	while(!L.empty()) L.pop();
	while(!R.empty()) R.pop();

	for(int i=n-1;i>=0;i--)
	{
		add(vec[i].fi,vec[i].se);
		ll cursum = 0;
		assert(L.size()==R.size());
		assert(L.top()<=R.top());
		cursum += rsum - lsum;
		dpr[i]=cursum;
	}

	for(int i = 0; i <= n; i++)
	{
		mini=min(mini,dpl[i]+dpr[i]);
		//cout<<i<<' '<<dpl[i]+dpr[i]<<'\n';
	}

	ans+=n;
	ans+=mini;
	cout<<ans<<'\n';
}

Compilation message (stderr)

bridge.cpp: In function 'void add(ll, ll)':
bridge.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(R.size()>siz)
                ^

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