제출 #585417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585417		GusterGoose27	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	331 ms	17484 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


const ll MAXN = 1e5;
ll k, n, m;
pii intervals[MAXN];
ll ans = 0;
ll best[MAXN];
ll bestrev[MAXN];
ordered_set divs;

struct comp {
	bool operator()(const pii &a, const pii &b) {
		return (a.first+a.second) < (b.first+b.second);
	}
} comp;

void rev() {
	for (ll i = 0; i < n; i++) {
		ll f = intervals[i].first;
		intervals[i].first = 1e9-intervals[i].second;
		intervals[i].second = 1e9-f;
	}
	for (ll i = 0; i < n/2; i++) {
		pii temp = intervals[i];
		intervals[i] = intervals[n-1-i];
		intervals[n-1-i] = temp;
	}
}

void makebests(ll best[]) {
	divs.clear();
	divs.insert(intervals[0].first);
	divs.insert(intervals[0].second);
	ll curbest = intervals[0].second-intervals[0].first;
	best[0] = curbest;
	for (ll i = 1; i < n; i++) {
		//ll prevl = divs.find_by_order(divs.size()/2-1);
		ll prevr = *(divs.find_by_order(divs.size()/2));
		divs.insert(intervals[i].first);
		divs.insert(intervals[i].second);
		assert(divs.size() % 2 == 0);
		// ll curl = divs.find_by_order(divs.size()/2-1);
		// ll curr = divs.find_by_order(divs.size()/2);
		best[i] = best[i-1]+intervals[i].second-intervals[i].first;
		if (intervals[i].first > prevr) best[i] += 2*(intervals[i].first-prevr);
	}
}

ll bash() {
	ll b = -1;
	for (int j = 0; j < 2*n; j++) {
		int pos;
		if (j < n) pos = intervals[j].first;
		else pos = intervals[j-n].second;
		ll cur = 0;
		for (int i = 0; i < n; i++) {
			cur += intervals[i].second-intervals[i].first;
			if (pos > intervals[i].second) cur += 2*(pos-intervals[i].second);
			if (pos < intervals[i].first) cur += 2*(intervals[i].first-pos);
		}
		if (b == -1 || cur < b) b = cur;
	}
	return b;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> k >> m;
	n = 0;
	for (ll i = 0; i < m; i++) {
		char c1, c2; ll l, r;
		cin >> c1 >> l >> c2 >> r;
		if (r < l) {
			ll temp = l;
			l = r;
			r = temp;
		}
		if (c1 == c2) {
			ans += r-l;
		}
		else {
			ans++;
			intervals[n++] = pii(l, r);
		}
	}
	if (n == 0) {
		cout << ans << "\n";
		return 0;
	}
	sort(intervals, intervals+n, comp);
	makebests(best);
	if (k == 1) {
		//ll b = bash();
		//assert(best[n-1] == b);
		cout << (ans+best[n-1]) << "\n";
		return 0;
	}
	rev();
	//sort(intervals, intervals+n, comp);
	makebests(bestrev);
	ll b = best[0]+bestrev[n-2];
	for (ll i = 1; i < n-1; i++) {
		if (best[i]+bestrev[n-2-i] < b) b = best[i]+bestrev[n-2-i];
	}
	cout << (b+ans) << "\n";
	return 0;
}

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