Submission #585404

#	Time	Username	Problem	Language	Result	Execution time	Memory
585404		GusterGoose27	Palembang Bridges (APIO15_bridge)	C++11	0 / 100	1 ms	340 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<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


const int MAXN = 1e5;
int 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 (int i = 0; i < n; i++) {
		int f = intervals[i].first;
		intervals[i].first = 1e9-intervals[i].second;
		intervals[i].second = 1e9-f;
	}
	for (int 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 (int i = 1; i < n; i++) {
		//int prevl = divs.find_by_order(divs.size()/2-1);
		int prevr = *(divs.find_by_order(divs.size()/2));
		divs.insert(intervals[i].first);
		divs.insert(intervals[i].second);
		assert(divs.size() % 2 == 0);
		// int curl = divs.find_by_order(divs.size()/2-1);
		// int 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);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> k >> m;
	for (int i = 0; i < m; i++) {
		char c1, c2; int l, r;
		cin >> c1 >> l >> c2 >> r;
		if (c1 == c2) {
			ans += r-l;
		}
		else {
			ans++;
			intervals[n++] = pii(l, r);
		}
	}
	sort(intervals, intervals+n, comp);
	makebests(best);
	if (k == 1) {
		cout << (ans+best[n-1]) << "\n";
		return 0;
	}
	rev();
	//sort(intervals, intervals+n, comp);
	makebests(bestrev);
	ll b = best[0]+bestrev[n-2];
	for (int 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: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37