oj.uz

Submission #17413

# Submission time Handle Problem Language Result Execution time Memory
17413 2015-11-30T02:00:17 Z comet Palembang Bridges (APIO15_bridge) C++
0 / 100
 0 ms 4300 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;

struct pt{
	ll x,y;
	bool operator<(const pt& r)const{
		return x+y<r.x+r.y;
	}
};

int K,N,sz;
ll base,ans,sum;
ll L[100010],R[100010];
pt a[100010];

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

void push(int x){
	if(!hi.empty()&&x>=hi.top())hi.push(x);
	else lo.push(x);
	ll t;
	while(hi.size()+1<lo.size()){
		t=lo.top();lo.pop();
		hi.push(t);
	}
	while(hi.size()>lo.size()+1){
		t=hi.top();hi.pop();
		lo.push(t);
	}
}

void f(ll s[]){
	for(int i=0;i<sz;i++){
		push(a[i].x);
		push(a[i].y);
		//printf("%lld %lld\n",lo.top(),hi.top());
		int mid=(lo.top()+hi.top())/2;
		for(int j=0;j<=i;j++){
			s[i]+=abs(a[j].x-mid);
			s[i]+=abs(a[j].y-mid);
		}
	}
}

int main(){
	//freopen("bridge.in","r",stdin);

	scanf("%d%d ",&K,&N);
	char tx,ty;
	ll x,y;
	for(int i=0;i<N;i++){
		scanf("%c %lld %c %lld ",&tx,&x,&ty,&y);
		if(tx==ty){
			base+=y-x-1;
		}else{
			a[sz++]=pt{x,y};
		}
	}
	base+=N;

	sort(a,a+sz);

	f(L);
	if(K==1){
		printf("%lld",L[sz-1]+base);
		return 0;
	}
	reverse(a,a+sz);
	f(R);

	ans=1e18;
	for(int i=0;i<sz-1;i++){
		ans=min(ans,L[i]+R[sz-2-i]);
	}

	printf("%lld",ans+base);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:60:14: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
    a[sz++]=pt{x,y};
              ^
bridge.cpp:52:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d ",&K,&N);
                      ^
bridge.cpp:56:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c %lld %c %lld ",&tx,&x,&ty,&y);
                                          ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4300 KB Output isn't correct
2 Halted 0 ms 0 KB -