Submission #213155

#	Time	Username	Problem	Language	Result	Execution time	Memory
213155		iris2617	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	118 ms	8040 KiB

bridge

#include <bits/stdc++.h>
#define int long long
#define iris 998244353
#define pii pair<int,int>
using namespace std;

vector<int> ouo; 
vector<pii> arr;
priority_queue<int> ll;
priority_queue<int,vector<int>,greater<int> > rr;
int lsum,rsum;
int ans[100010];

bool cmp(pii a,pii b)
{
	return a.first+a.second<b.first+b.second;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	char x,y;
	int k,n,i,a,b,sum,sagiri,l,r,m;
	sum=0;
	cin>>k>>n;
	for(i=0;i<n;i++)
	{
		cin>>x>>a>>y>>b;
		if(x==y)
		{
			sum+=abs(a-b);
		}
		else
		{
			sum++;
			if(k==1)
			{
				ouo.emplace_back(a);
				ouo.emplace_back(b);
			}
			else
			{
				arr.emplace_back(make_pair(a,b));
			}
		}
	}
	
	if(ouo.empty() && arr.empty())
	{
		cout<<sum<<'\n';
		return 0;
	}
	
	if(k==1)
	{
		sort(ouo.begin(), ouo.end());
		m=ouo[ouo.size()/2];
		for(int aoi:ouo)
		{
			sum+=abs(aoi-m);
		}
		cout<<sum<<'\n';
	}
	else
	{
		sort(arr.begin(), arr.end(), cmp);
		lsum=rsum=0;
		for(i=0;i<arr.size();i++)
		{
			l=arr[i].first;
			r=arr[i].second;
			
			ll.push(l);
			ll.push(r); 
			lsum+=l+r;
			
			while(!ll.empty() && !rr.empty() && ll.top()>rr.top())
			{
				rsum+=ll.top();
				lsum-=ll.top();
				rr.push(ll.top());
				ll.pop();
			}
			while(ll.size()+1 < rr.size())
			{
				lsum+=rr.top();
				rsum-=rr.top();
				ll.push(rr.top());
				rr.pop();
			}
			while(ll.size() > rr.size())
			{
				rsum+=ll.top();
				lsum-=ll.top();
				rr.push(ll.top());
				ll.pop();
			}
			m=ll.top();
			ans[i+1]=m*ll.size()-lsum+rsum-m*rr.size();
		}
		while(!ll.empty())
			ll.pop();
		while(!rr.empty())
			rr.pop();
		sagiri=1e18;
		lsum=rsum=0;
		for(i=arr.size()-1;i>=0;i--)
		{
			l=arr[i].first;
			r=arr[i].second;
			
			ll.push(l);
			ll.push(r);
			lsum+=l+r;
			
			while(!ll.empty() && !rr.empty() && ll.top()>rr.top())
			{
				rsum+=ll.top();
				lsum-=ll.top();
				rr.push(ll.top());
				ll.pop();
			}
			while(ll.size()+1 < rr.size())
			{
				lsum+=rr.top();
				rsum-=rr.top();
				ll.push(rr.top());
				rr.pop();
			}
			while(ll.size() > rr.size())
			{
				rsum+=ll.top();
				lsum-=ll.top();
				rr.push(ll.top());
				ll.pop();
			}
			m=ll.top();
			ans[i]+=m*ll.size()-lsum+rsum-m*rr.size();
			sagiri=min(sagiri, ans[i]);
		}
		cout<<sagiri+sum<<'\n';
	}
	
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:69:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<arr.size();i++)
           ~^~~~~~~~~~~

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