Submission #17578

#	Time	Username	Problem	Language	Result	Execution time	Memory
17578		comet	Palembang Bridges (APIO15_bridge)	C++98	22 / 100	129 ms	12148 KiB

bridge

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cassert>
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 lu[200010];
int sz;

ll base;

ll sum[200010],cnt[200010];

ll L[100010],R[100010];

void add(ll tree[],int x,ll c){
	x++;
	while(x<sz){
		tree[x]+=c;
		x+=x&-x;
	}
}

ll query(ll tree[],int x){
	x++;
	ll ret=0;
	while(x){
		ret+=tree[x];
		x-=x&-x;
	}
	return ret;
}

void compress(){
	for(int i=0;i<n;i++){
		lu[sz++]=a[i].x;
		lu[sz++]=a[i].y;
	}
	sort(lu,lu+sz);
	sz=unique(lu,lu+sz)-lu;
	for(int i=0;i<n;i++){
		a[i].x=lower_bound(lu,lu+sz,a[i].x)-lu;
		a[i].y=lower_bound(lu,lu+sz,a[i].y)-lu;
	}
}

priority_queue<int> lo;
priority_queue<int,vector<int>,greater<int> > hi;

void init(){
	while(!lo.empty())lo.pop();
	while(!hi.empty())hi.pop();
	memset(sum,0,sizeof(sum));
	memset(cnt,0,sizeof(cnt));
}

void push(ll x,ll& Sum){
	Sum+=lu[x];
	add(sum,x,lu[x]);
	add(cnt,x,1);
	if(lo.empty())lo.push(x);
	else{
		if(lo.top()>=x)lo.push(x);
		else hi.push(x);
		while(hi.size()>lo.size()){
			ll t=hi.top();hi.pop();
			lo.push(t);
		}
		while(lo.size()>hi.size()+1){
			ll t=lo.top();lo.pop();
			hi.push(t);
		}
	}
}

ll getMid(){
	return lo.top();
}

void f(ll d[]){

	init();
	
	ll mid,loSum,loCnt,hiSum,hiCnt,Sum=0;

	for(int i=0;i<n;i++){
		push(a[i].x,Sum);
		push(a[i].y,Sum);
		
		mid = getMid();
		loSum = query(sum,mid);
		loCnt = query(cnt,mid);
		hiSum = Sum-loSum;
		hiCnt = (i+1)*2 - loCnt;
		d[i] = (lu[mid]*loCnt-loSum) + (hiSum-lu[mid]*hiCnt);

//		printf("mid : %lld(%lld)\n",mid,lu[mid]);
//		printf("%lld %lld %lld %lld : %lld\n",loSum,loCnt,hiSum,hiCnt,d[i]);
	}
}

vector<ll> s;

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);
		}
	}

	compress();

	sort(a,a+n);

	ll ans=1e18;

	if(K==1){
		/*
		f(L);
		printf("%lld",L[n-1]+base);
		*/
		for(int i=0;i<n;i++){
			s.push_back(a[i].x);
			s.push_back(a[i].y);
		}
		sort(s.begin(),s.end());
		ans=0;
		for(int i=0;i<s.size();i++){
			ans+=abs(lu[s[i]]-lu[s[s.size()/2]]);
		}
		printf("%lld\n",ans+base);
	}else{
		f(L);
		reverse(a,a+n);
		f(R);
		for(int i=0;i<n-1;i++){
			ans = min(ans,L[i]+R[n-i-2]);
		}
		printf("%lld",ans+base);
	}

	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:148:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++){
                ^
bridge.cpp:117: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:121: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: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37