Submission #443593

#	Time	Username	Problem	Language	Result	Execution time	Memory
443593		8e7	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	130 ms	5556 KiB

bridge

//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <utility>
#include <assert.h>
using namespace std;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define ld long double
#define maxn 100005
#define pii pair<int, int>
#define pdd pair<double, double>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
pii a[maxn];
ll pref[maxn], suf[maxn];
void solve(int n, pii arr[], ll ans[]) {
	ll lc = 0, rc = 0, cur = 0, cost = 0;
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	for (int i = 0;i < n;i++) {
		pq.push({arr[i].ff, 0}), rc++, cost += arr[i].ff - cur;
		pq.push({arr[i].ss, 1});
	}
	while (pq.size()) {
		pii seg = pq.top();pq.pop();
		ll dis = seg.ff - cur;
		if ((lc - rc) * dis <= 0) {
			cost += (lc - rc) * dis;
			cur = seg.ff;
			if (seg.ss == 0) rc--;
			else lc++;
		} else {
			pq.push(seg);
			break;
		}
	}
	ans[n - 1] = cost;

	/*
	for (int i = 0;i < n;i++) {
		//debug(arr[i].ff, arr[i].ss);
		if (arr[i].ff > cur) pq.push({arr[i].ff, 0}), rc++, cost += arr[i].ff - cur;	
		pq.push({arr[i].ss, 1});
		while (pq.size()) {
			pii seg = pq.top();pq.pop();
			ll dis = seg.ff - cur;
			if ((lc - rc) * dis <= 0) {
				cost += (lc - rc) * dis;
				cur = seg.ff;
				if (seg.ss == 0) rc--;
				else lc++;
			} else {
				pq.push(seg);
				break;
			}
		}
		ans[i] = cost;
	}
	*/
}
int main() {
	int k, n;
	cin >> k >> n;
	int cross = 0;
	ll sum = 0;
	int m = 0;
	for (int i = 0;i < n;i++) {
		char p, q;
		int s, t;
		cin >> p >> s >> q >> t;
		if (s > t) swap(s, t);
		sum += t - s;
		if (p != q) {
			a[m++] = {s, t};	
		}
	}
	sort(a, a + m, [&](pii x, pii y) {return x.ff + x.ss < y.ff + y.ss;});
	//sort(a, a + m);
	solve(m, a, pref);
	//pary(pref, pref + m);
	cout << 2 * pref[m - 1] + sum + m << endl;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
   */

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:73:6: warning: unused variable 'cross' [-Wunused-variable]
   73 |  int cross = 0;
      |      ^~~~~

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