Submission #650883

#	Time	Username	Problem	Language	Result	Execution time	Memory
650883		AmirH	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	443 ms	15928 KiB

bridge

#include<bits/stdc++.h>


using namespace std;
typedef long long int ll;


#define pb push_back
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int, int>

const int MAX_N = 2e5+25;

ll n, k;
vector<pair<ll, pair<ll, ll>>> v;
vector<pair<ll, ll>> vtx;
ll sum = 0;
multiset<ll> a, b;
multiset<ll> c, d;
ll suma, sumb, sumc, sumd;
ll mini = 1e18;

void print() {
	ll res = 0;
	ll p1 = 0;
	ll p2 = 0;
	ll p3 = 0;
	ll p4 = 0;
	if(a.size() > 0)
		p1 = ((*a.rbegin()) * a.size()) - suma;
	if(b.size() > 0)
		p2 = sumb - ((*a.rbegin()) * b.size());
	if(c.size() > 0) 
		p3 += ((*c.rbegin()) * c.size()) - sumc;
	if(d.size() > 0)
		p4 += sumd - ((*c.rbegin()) * d.size());
	res = p1 + p2 + p3 + p4;
 	mini = min(mini, res);
}

void handle(multiset<ll> & s, multiset<ll> & f, ll & sum1, ll & sum2) {
	while(s.size() > f.size() && s.size() - f.size() >= 2) {
		ll x = *s.rbegin();
		sum1 -= x;
		sum2 += x;
		s.erase(s.find(x));
		f.insert(x);
	}
	while(f.size() > s.size()) {
		ll x = *f.begin();
		sum1 += x;
		sum2 -= x;
		f.erase(f.begin());
		s.insert(x);
	}
}

void add(int y) {
	if(a.size() == 0) {
		a.insert(y);
		suma += y;
	}
	else {
		if(y > *a.rbegin()) {
			sumb += y;
			b.insert(y);
		}
		else {
			suma += y;
			a.insert(y);
		}
	}
	if(y > *c.rbegin()) {
		d.erase(d.find(y));
		sumd -= y;
	}
	else {
		sumc -= y;
		c.erase(c.find(y));
	}
	handle(a, b, suma, sumb);
	handle(c, d, sumc, sumd);
}

void solve() {
	sort(v.begin(), v.end());
	for(auto i : v) {
		vtx.pb({i.second.first, i.second.second});
	}
	for(auto i : vtx) {
		c.insert(i.first);
		c.insert(i.second);
		sumc += i.first;
		sumc += i.second;
	}
	handle(c, d, sumc, sumd);
	print();
	for(int i = 0; i < vtx.size(); i++) {
		add(vtx[i].first);
		add(vtx[i].second);
		print();
	}
}

void input() {
	cin >> k >> n;
	if(k == 1) {
		vector<int> cnt;
		for(int i = 1; i <= n; i++) {
			char a, b; 
			ll x, y;
			cin >> a >> x >> b >> y;
			if(a != b) {
				sum++;
				cnt.pb(x);
				cnt.pb(y);
			}
			else {
				sum += abs(x - y);
			}
		}
		sort(cnt.begin(), cnt.end());
		ll mid = cnt[(cnt.size() - 1) / 2];
		for(auto i : cnt) {
			sum += abs(i - mid);
		}
		cout << sum;
	}
	else {
		for(int i = 1; i <= n; i++) {
			char a, b; 
			ll x, y;
			cin >> a >> x >> b >> y;
			if(a != b)
				v.pb({x + y, {x, y}});
			else
				sum += abs(x - y);
		}
		if(v.size() == 0)
			cout << sum;
		else {
			solve();
			cout << sum + mini + v.size();
		}
	}
}

int main() {
	faster;
	input();
}

Compilation message (stderr)

bridge.cpp: In function 'void solve()':
bridge.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i = 0; i < vtx.size(); i++) {
      |                 ~~^~~~~~~~~~~~

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