제출 #1034803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034803		Tob	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	557 ms	42884 KiB

bridge

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7;

int n, k;
int l[N], r[N], l_[N], r_[N], ind[N];

int main () {
	FIO;
	cin >> k >> n;
	
	ll res = 0;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int a, b;
		char c1, c2;
		cin >> c1 >> a >> c2 >> b;
		if (c1 == c2) res += abs(a-b);
		else {
			res++;
			l_[cnt] = min(a, b);
			r_[cnt++] = max(a, b);
		}
	}
	for (int i = 0; i < cnt; i++) ind[i] = i;
	
	sort(ind, ind+cnt, [&](int x, int y) {return l_[x]+r_[x] < l_[y]+r_[y];});
	for (int i = 0; i < cnt; i++) l[i] = l_[ind[i]], r[i] = r_[ind[i]];
	
	if (k == 1) {
		multiset <int> s;
		ll d = -2*cnt, h = 0;
		for (int i = 0; i < cnt; i++) {
			s.insert(l[i]);
			s.insert(r[i]);
			h += l[i]+r[i];
		}
		for (int i = 0; i < cnt; i++) s.erase(--s.end());
		int la = 0;
		for (auto x : s) {
			h += d*(x-la);
			la = x;
			d += 2;
		}
		res += h;
	}
	else {
		set <pii> s;
		map <ll, ll> ma;
		ll y = -1, z = 0, h = 0;
		auto add = [&](ll x) {
			s.insert({x, ma[x]++});
			s.insert({x, ma[x]++});
			if (y == -1) {y = s.begin() -> F; return;}
			h += abs(y-x);
			auto p = s.find({y, z});
			if (x >= y) ++p;
			else --p;
			pii ny = *p;
			h -= max(0LL, ny.F-y);
			y = ny.F;
			z = ny.S;
		};
		vector <ll> pre(cnt+1, 0);
		for (int i = 0; i < cnt; i++) {
			add(l[i]);
			add(r[i]);
			pre[i+1] = h;
		}
		s.clear();
		ma.clear();
		y = -1; z = 0; h = 0;
		ll mn = pre[cnt];
		for (int i = cnt-1; i >= 0; i--) {
			add(l[i]);
			add(r[i]);
			mn = min(mn, pre[i]+h);
		}
		res += mn;
	}
	
	cout << res << "\n";

	return 0;
}

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