Submission #216727

#	Time	Username	Problem	Language	Result	Execution time	Memory
216727		MetB	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	230 ms	8036 KiB

bridge

#include <bits/stdc++.h>
 
#define N 1000001
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

ll n, k, median;

ll side = 0, lsum = 0, rsum = 0;
ll pr[N];

priority_queue <ll> l, r;

struct seg {
	ll l, r;

	bool operator < (const seg& b) {
		return l + r < b.l + b.r;
	}
};

vector <seg> v;

void insert (ll x) {
	if (!l.size ()) {
		median = x;
		l.push (x);
		lsum += x;

		return;
	}

	if (x <= median) { l.push (x), lsum += x; }
	else { r.push (-x), rsum += x; }

	ll len = (l.size () + r.size () + 1) / 2;

	if (l.size () > len) {
		ll k = l.top ();
		l.pop ();
		r.push (-k);
		lsum -= k, rsum += k;
	}

	if (l.size () < len) {
		ll k = -r.top ();
		r.pop ();
		l.push (k);	
		lsum += k, rsum -= k;
	}

	median = l.top ();
}

int main () {
	cin >> k >> n;

	for (ll i = 0; i < n; i++) {
		string a, b;
		ll la, lb;
		cin >> a >> la >> b >> lb;
		if (a == b) side += abs (la - lb);
		else v.push_back ({la, lb});
	}

	sort (v.begin (), v.end ());


	for (ll i = 0; i < v.size (); i++) {
		insert (v[i].l), insert (v[i].r);
		pr[i] = rsum - lsum;
	}

	ll n = v.size ();


	if (k == 2) {
		lsum = 0, rsum = 0;
		
		while (!l.empty ()) l.pop ();
		while (!r.empty ()) r.pop ();

		ll mx = pr[n-1];

		for (ll i = n - 1; i >= 0; i--) {
			insert (v[i].l), insert (v[i].r);
			mx = min (mx, rsum - lsum + (i ? pr[i-1] : 0));
		}

		cout << mx + side + n;
	}
	else cout << pr[n-1] + side + n;
}

Compilation message (stderr)

bridge.cpp: In function 'void insert(ll)':
bridge.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (l.size () > len) {
      ~~~~~~~~~~^~~~~
bridge.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (l.size () < len) {
      ~~~~~~~~~~^~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (ll i = 0; i < v.size (); i++) {
                 ~~^~~~~~~~~~~

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