Submission #15866

#	Time	Username	Problem	Language	Result	Execution time	Memory
15866		myungwoo	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	86 ms	6324 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

#define MAXN 100005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long lld;

int K, N, M;
lld D[MAXN], E[MAXN];

struct Z{
	int a, b;
} A[MAXN];

void proc(lld V[])
{
	if (!N) return;
	lld val = abs(A[1].a - A[1].b);
	priority_queue <int> p, q;
	int mid = A[1].a;
	if (A[1].b < mid) p.push(A[1].b);
	else q.push(-A[1].b);
	V[1] = val;
	for (int i=2;i<=N;i++){
		val += abs(mid - A[i].a) + abs(mid - A[i].b);
		if (A[i].a < mid) p.push(A[i].a);
		else q.push(-A[i].a);
		if (A[i].b < mid) p.push(A[i].b);
		else q.push(-A[i].b);
		while (sz(p) < sz(q)){
			int nxt = -q.top(); q.pop();
			p.push(mid);
			val += (lld)(nxt - mid) * sz(p) - (lld)(nxt - mid) * (sz(q) + 1);
			mid = nxt;
		}
		while (sz(p) > sz(q)+1){
			int nxt = p.top(); p.pop();
			q.push(-mid);
			val += (lld)(mid - nxt) * sz(q) - (lld)(mid - nxt) * (sz(p) + 1);
			mid = nxt;
		}
		V[i] = val;
	}
}

int main()
{
	scanf("%d%d", &K, &M);
	vector <int> arr;
	lld def = 0;
	while (M--){
		char p, q; int a, b;
		scanf(" %c%d %c%d", &p, &a, &q, &b);
		if (p == q){ def += abs(a-b); continue; }
		A[++N] = {a, b};
	}
	sort(A+1, A+N+1, [](const Z &a, const Z &b){
		return a.a+a.b < b.a+b.b;
	});
	proc(D);
	if (K == 1){ printf("%lld\n", D[N] + def + N); return 0; }
	reverse(A+1, A+N+1);
	proc(E);
	lld ans = 1e18;
	for (int i=0;i<=N;i++) ans = min(ans, def + D[i] + E[N-i] + N);
	printf("%lld\n", ans);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:50:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &K, &M);
                       ^
bridge.cpp:55:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d %c%d", &p, &a, &q, &b);
                                      ^

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