Submission #915733

#	Time	Username	Problem	Language	Result	Execution time	Memory
915733		tvladm2009	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	33 ms	4696 KiB

bridge

#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	int k, n;
	cin >> k >> n;
	ll add = 0;
	vector<pair<int, int>> v;
	vector<int> points;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		char p, q;
		int s, t;
		cin >> p >> s >> q >> t;
		if (p == q) {
			add += abs(s - t);
		} else {
			points.pb(s);
			points.pb(t);
			v.pb(mp(s, t));
			cnt++;
		}
	}
	if (k == 1) {
		sort(all(points));
		auto f = [&](int bridge) {
			ll res = 0;
			for (auto i: points) {
				res += abs(i - bridge);
			}
			res += cnt;
			return res;
		};
		
		int med = (sz(points) + 1) / 2;
		cout << f(points[med - 1]) + add << '\n';
	} else {
		sort(all(v), [&](pair<int, int> a, pair<int, int> b) {
			return a.first + a.second < b.first + b.second;
		});		
		priority_queue<int> pql;
		priority_queue<int, vector<int>, greater<int>> pqr;
		ll lsum = 0, rsum = 0;
		auto insert = [&](int x) {
			int med = (pql.size() ? pql.top() : 1e9 + 10);
			if (x <= med) {
				pql.push(x);
				lsum += x;
			} else {
				pqr.push(x);
				rsum += x;
			}
			
			if (pqr.size() + 1 < pql.size()) {
				int nxt = pql.top();
				pql.pop();
				pqr.push(nxt);
				lsum -= nxt;
				rsum += nxt;
			} else if (pql.size() < pqr.size()) {
				int nxt = pqr.top();
				pqr.pop();
				pql.push(nxt);
				rsum -= nxt;
				lsum += nxt;
			}
		};
		vector<int> pref(sz(v) + 1);
		for (int i = 1; i <= sz(v); i++) {
			insert(v[i - 1].first);
			insert(v[i - 1].second);
			pref[i] = rsum - lsum;
		}
		while (!pql.empty()) {
			pql.pop();
		}
		while (!pqr.empty()) {
			pqr.pop();
		}
		lsum = 0;
		rsum = 0;
		ll ans = pref[sz(v)];
		for (int i = sz(v); i >= 1; i--) {
			insert(v[i - 1].first);
			insert(v[i - 1].second);
			chkmin(ans, rsum - lsum + pref[i - 1]);
		}
		cout << ans + add + cnt << '\n';
	}
	return 0;
}

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