Submission #17575

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
17575	2015-12-29T03:03:59 Z	comet	Palembang Bridges (APIO15_bridge)	C++	Compilation error	0 ms	0 KB

bridge

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

int N,K,n;
struct pp{
	ll x,y;
}a[100010];

ll lu[200010];
int sz;

ll base;

ll sum[200010],cnt[200010];

ll L[100000],R[100000];

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

}

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,[](const pp& i,const pp& j){
		return i.x+i.y<j.x+j.y;
	});

	ll ans=1e18;

	if(K==1){
		f(L);
		printf("%lld\n",L[n-1]+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\n",ans+base);
	}

	return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:130:2: warning: lambda expressions only available with -std=c++11 or -std=gnu++11
  });
  ^
bridge.cpp:130:3: error: no matching function for call to 'sort(pp [100010], pp*, main()::<lambda(const pp&, const pp&)>)'
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from bridge.cpp:2:
/usr/include/c++/5/bits/stl_algo.h:4689:5: note: candidate: template<class _RAIter> void std::sort(_RAIter, _RAIter)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
     ^
/usr/include/c++/5/bits/stl_algo.h:4689:5: note:   template argument deduction/substitution failed:
bridge.cpp:130:3: note:   candidate expects 2 arguments, 3 provided
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from bridge.cpp:2:
/usr/include/c++/5/bits/stl_algo.h:4718:5: note: candidate: template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^
/usr/include/c++/5/bits/stl_algo.h:4718:5: note:   template argument deduction/substitution failed:
bridge.cpp: In substitution of 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = pp*; _Compare = main()::<lambda(const pp&, const pp&)>]':
bridge.cpp:130:3:   required from here
bridge.cpp:130:3: error: template argument for 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)' uses local type 'main()::<lambda(const pp&, const pp&)>'
  });
   ^
bridge.cpp:130:3: error:   trying to instantiate 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)'
bridge.cpp:112: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:116: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);
                                          ^