oj.uz

Submission #17582

# Submission time Handle Problem Language Result Execution time Memory
17582 2015-12-29T03:35:06 Z comet Palembang Bridges (APIO15_bridge) C++
0 / 100
 0 ms 9000 KB 
#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 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<ll> lo;
priority_queue<ll,vector<ll>,greater<ll> > 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)*2ll - 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]);
	}
}

void DM(){

	base=0;
	FILE* out = fopen(".in","w");

	int N = rand()%10+2;
	fprintf(out,"%d %d\n",1,N);
	for(int i=0;i<N;i++){
		fprintf(out,"A %d B %d\n",rand(),rand());
	}
	fclose(out);

	freopen(".in","r",stdin);

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

	compress();

	sort(a,a+n);

	ll ans=1e18;

	if(K==1){

		f(L);
		
		vector<ll> s;
		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]]);
		}
		
		if(ans == L[n-1]){
			//puts("Success!");
		}else{
			puts("Fail!");
			exit(0);
		}

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

int main(){

	base = 0;
	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;
	}

	compress();

	sort(a,a+n);

	ll ans;

	if(K==1){
		f(L);
		printf("%lld\n",L[n-1]+base);

	}else{
		f(L);
		reverse(a,a+n);
		f(R);
		ans = L[n-1];
		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 'void DM()':
bridge.cpp:165:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++){
                ^
bridge.cpp:127:26: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen(".in","r",stdin);
                          ^
bridge.cpp:129: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:133: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);
                                          ^
bridge.cpp: In function 'int main()':
bridge.cpp:190: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:194: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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9000 KB Output is correct
2 Correct 0 ms 9000 KB Output is correct
3 Incorrect 0 ms 9000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9000 KB Output is correct
2 Correct 0 ms 9000 KB Output is correct
3 Incorrect 0 ms 9000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9000 KB Output is correct
2 Correct 0 ms 9000 KB Output is correct
3 Incorrect 0 ms 9000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9000 KB Output is correct
2 Correct 0 ms 9000 KB Output is correct
3 Incorrect 0 ms 9000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9000 KB Output is correct
2 Correct 0 ms 9000 KB Output is correct
3 Incorrect 0 ms 9000 KB Output isn't correct
4 Halted 0 ms 0 KB -