Submission #107212

#	Time	Username	Problem	Language	Result	Execution time	Memory
107212		nxteru	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	132 ms	7668 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
struct t{
	ll a,b;
	bool operator<(const t&q)const{
		return a+b<q.a+q.b;
	}
	bool operator>(const t&q)const{
		return a+b>q.a+q.b;
	}
};
struct mid{
	priority_queue<ll>d;
	priority_queue<ll,vector<ll>,greater<ll> >u;
	ll ds,us;
	void ini(void){
		ds=0,us=0;
		while(!d.empty())d.pop();
		while(!u.empty())u.pop();
	}
	void pushd(ll x){
		d.push(x);
		ds+=x;
	}
	void pushu(ll x){
		u.push(x);
		us+=x;
	}
	ll popd(void){
		ll res=d.top();
		d.pop();
		ds-=res;
		return res;
	}
	ll popu(void){
		ll res=u.top();
		u.pop();
		us-=res;
		return res;
	}
	void up(void){
		pushu(popd());
	}
	void down(void){
		pushd(popu());
	}
	void push(ll x){
		if(u.size()==0||u.top()<=x)pushu(x);
		else pushd(x);
		while(u.size()>d.size()+1)down();
		while(u.size()<d.size())up();
	}
	ll que(void){
		ll res=us-ds;
		if(u.size()>d.size())res-=u.top();
		return res;
	}
};
int n,k;
ll s,l[100005],r[100005];
vector<t>p;
mid q;
int main(void){
    scanf("%d%d",&k,&n);
    for(int i=0;i<n;i++){
		char x,y;
		ll a,b;
		scanf(" %c %lld %c %lld",&x,&a,&y,&b);
		if(x==y)s+=abs(a-b);
		else{
			p.PB(t{a,b});
			s++;
		}
	}
	n=p.size();
	sort(p.begin(),p.end());
	q.ini();
	for(int i=0;i<n;i++){
		q.push(p[i].a);
		q.push(p[i].b);
		l[i]=q.que();
	}
	q.ini();
	for(int i=n-1;i>=0;i--){
		q.push(p[i].a);
		q.push(p[i].b);
		r[i]=q.que();
	}
	ll ans=r[0];
	for(int i=0;i<n;i++)ans=min(ans,l[i]+r[i+1]);
	if(k==1)printf("%lld\n",l[n-1]+s);
	else printf("%lld\n",ans+s);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&k,&n);
     ~~~~~^~~~~~~~~~~~~~
bridge.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %lld %c %lld",&x,&a,&y,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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