Submission #17588

#	Time	Username	Problem	Language	Result	Execution time	Memory
17588		comet	Palembang Bridges (APIO15_bridge)	C++98	100 / 100	126 ms	7032 KiB

bridge

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cassert>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long ll;

int N,K,n;
struct pp{
	ll x,y;
	bool operator<(const pp& r)const{
		return x+y<r.x+r.y;
	}
}a[100010];

ll base;
ll L[100010],R[100010];

priority_queue<ll> lo;
priority_queue<ll,vector<ll>,greater<ll> > hi;
ll loSum,hiSum;

void init(){
	while(!lo.empty())lo.pop();
	while(!hi.empty())hi.pop();
	loSum=hiSum=0;
}

void push(ll x){
	if(lo.size()==hi.size())lo.push(x),loSum+=x;
	else hi.push(x),hiSum+=x;
	
	if(!lo.empty()&&!hi.empty()&&lo.top()>hi.top()){
		ll a=lo.top(),b=hi.top();
		lo.pop();hi.pop();
		loSum-=a,hiSum-=b;
		lo.push(b),hi.push(a);
		loSum+=b,hiSum+=a;
	}
}

ll query(ll i){
	i++;
	ll mid = lo.top();
	return i*mid-loSum + hiSum-i*mid;
}

void f(ll d[]){
	init();
	for(ll i=0;i<n;i++){
		push(a[i].x);
		push(a[i].y);
		d[i] = query(i);
	}
}

int main(){
	scanf("%d%d",&K,&N);
	char t1,t2;
	ll x,y;
	for(int i=0;i<N;i++){
		scanf(" %c %lld %c %lld",&t1,&x,&t2,&y);
		if(t1!=t2){
			a[n].x=min(x,y);
			a[n++].y=max(x,y);
			base++;
		}else{
			base+=abs(x-y);
		}
	}

	if(n==0){
		printf("%lld\n",base);
		return 0;
	}

	sort(a,a+n);

	if(K==1){
		f(L);
		printf("%lld\n",L[n-1]+base);
	}else{
		f(L);
		reverse(a,a+n);
		f(R);
		ll ans = L[n-1];
		for(int i=0;i<n-1;i++){
			ans = min(ans,L[i]+R[n-2-i]);
		}
		printf("%lld\n",ans+base);
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:62:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&K,&N);
                     ^
bridge.cpp:66:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %lld %c %lld",&t1,&x,&t2,&y);
                                          ^

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