Submission #569065

#	Time	Username	Problem	Language	Result	Execution time	Memory
569065		hollwo_pelw	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	105 ms	6240 KiB

bridge

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

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 1e5 + 5;

int n, k;
long long pre[N], suf[N], extra;
vector<pair<int, int>> seg;

struct median_pq {
	priority_queue<int> pql, pqr;
	long long suml = 0, sumr = 0;

	inline void clear() {
		suml = sumr = 0;
		while (!pql.empty()) pql.pop();
		while (!pqr.empty()) pqr.pop();
	}

	inline void push(int a, int b) {
		pql.push(+a), suml += a;
		pqr.push(-b), sumr += b;

		if (pql.top() > - pqr.top()) {
			a = pql.top();
			b = pqr.top();

			pql.pop();
			pqr.pop();
			
			pql.push(-b);
			pqr.push(-a);

			suml = suml - a - b;
			sumr = sumr + a + b;
		}
	}

	inline long long get() {
		return sumr - suml;
	}
} pq;

void Hollwo_Pelw(){
	cin >> k >> n;
	for (int i = 0; i < n; i++) {
		char ta, tb; int pa, pb;
		cin >> ta >> pa >> tb >> pb;
		if (pa > pb) swap(pa, pb);
		if (ta == tb) {
			extra += abs(pa - pb);
		}
		else {
			seg.emplace_back(pa, pb);
		}
	}
	n = seg.size(), extra += n;
	
	sort(seg.begin(), seg.end(), [&](const pair<int, int> &a, const pair<int, int> &b){
		return a.first + a.second < b.first + b.second;
	});

	pq.clear();
	for (int i = 0; i < n; i++) {
		pq.push(seg[i].first, seg[i].second);
		pre[i + 1] = pq.get();
		// cout << "add " << seg[i].first << ' ' << seg[i].second << '\n' << pq.get() << '\n';
	}

	pq.clear();
	for (int i = n; i --; ) {
		pq.push(seg[i].first, seg[i].second);
		suf[i + 1] = pq.get();
		// cout << "add " << seg[i].first << ' ' << seg[i].second << '\n' << pq.get() << '\n';
	}

	long long res = pre[n];
	
	if (k == 1) {
		cout << res + extra << '\n';
		return ;
	}

	for (int i = 1; i <= n; i++)
		res = min(res, pre[i - 1] + suf[i]);

	cout << res + extra << '\n';
}

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