Submission #14389

#	Time	Username	Problem	Language	Result	Execution time	Memory
14389		kriii	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	1323 ms	22008 KiB

bridge

#include <stdio.h>
#include <functional>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;

struct intv{
	intv(long long s_, long long e_){
		s = s_; e = e_;
	}
	long long s,e;
};
bool cmpm(const intv &a, const intv &b){return a.s + a.e < b.s + b.e;}
vector<intv> seg;
set<int> xs;

map<int, int, greater<int> > A[2]; long long sza[2],sa[2];
map<int, int> B[2]; long long szb[2],sb[2];

int K,N;

void push(int i, int x)
{
	A[i][x]++; sza[i]++; sa[i] += x;
	int p = A[i].begin()->first;
	B[i][p]++; szb[i]++; sb[i] += p;
	if (--A[i][p] == 0) A[i].erase(p); sza[i]--; sa[i] -= p;
	if (szb[i] > sza[i]){
		p = B[i].begin()->first;
		A[i][p]++; sza[i]++; sa[i] += p;
		if (--B[i][p] == 0) B[i].erase(p); szb[i]--; sb[i] -= p;
	}
}

void pop(int i, int x)
{
	if (A[i].count(x)){
		if (--A[i][x] == 0) A[i].erase(x); sza[i]--; sa[i] -= x;
	}
	else if (B[i].count(x)){
		if (--B[i][x] == 0) B[i].erase(x); szb[i]--; sb[i] -= x;
	}
	while (sza[i] >= szb[i] + 2){
		int p = A[i].begin()->first;
		B[i][p]++; szb[i]++; sb[i] += p;
		if (--A[i][p] == 0) A[i].erase(p); sza[i]--; sa[i] -= p;
	}
	while (sza[i] + 1 <= szb[i]){
		int p = B[i].begin()->first;
		A[i][p]++; sza[i]++; sa[i] += p;
		if (--B[i][p] == 0) B[i].erase(p); szb[i]--; sb[i] -= p;
	}
}

long long sum(int i)
{
	if (A[i].empty()) return 0;
	long long pos = A[i].begin()->first, res = 0;
	res += pos * sza[i] - sa[i];
	res += sb[i] - pos * szb[i];
	return res;
}

int main()
{
	long long ans = 0;
	scanf ("%d %d ",&K,&N);
	while (N--){
		char a,b; int x,y;
		scanf ("%c %d %c %d ",&a,&x,&b,&y);
		if (a == b){
			ans += abs(x-y);
		}
		else{
			ans++;
			if (x > y) swap(x,y);
			seg.push_back(intv(x,y));

			push(0,x); push(0,y);
			xs.insert(x); xs.insert(y);
		}
	}

	if (K == 1){
		ans += sum(0);
	}
	else{
		sort(seg.begin(),seg.end(),cmpm);
		long long good = sum(0);
		for (auto p : seg){
			push(1,p.s); push(1,p.e);
			pop(0,p.s); pop(0,p.e);
			good = min(good,sum(0)+sum(1));
		}
		ans += good;
	}

	printf ("%lld\n",ans);

	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:69:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d ",&K,&N);
                        ^
bridge.cpp:72:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%c %d %c %d ",&a,&x,&b,&y);
                                     ^

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