제출 #1267412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267412		ChuanChen	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	197 ms	10528 KiB

bridge

#include<bits/stdc++.h>
#define debug(v) //cerr << #v << ": " << v << '\n';
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int k, n;
ll ans;
vector<pii> inter;
bool cmp(pii a, pii b){
	return a.first+a.second < b.first+b.second;
}

struct two_set{
	multiset<int> s1, s2;
	//s1-> smaller or equal than mid
	//s2 -> greater or equal than mid;
	//s1.size() >= s2.size();
	ll sum1, sum2; 

	ll median(){
		if(s1.empty()){
			// cerr << "empty set\n";
			return 0;
		}
		return *s1.rbegin();
	}

	void add(int v){
		if(s1.empty()){
			s1.insert(v);
			sum1 += v;
			return;
		}

		if(s1.size() == s2.size()){
			if(v <= *s2.begin()){
				sum1 += v;
				s1.insert(v);
			}
			else{
				sum2 += v;
				s2.insert(v);

				sum1 += *s2.begin();
				s1.insert( *s2.begin() );

				sum2 -= *s2.begin();
				s2.erase(s2.begin());
			}
		}
		else{
			if(v <= *s1.rbegin()){
				sum2 += *(--s1.end());
				s2.insert( *(--s1.end()) );

				sum1 -= *(--s1.end());
				s1.erase( --s1.end() );

				sum1 += v;
				s1.insert(v);
			}
			else{
				sum2 += v;
				s2.insert(v);
			}
		}
	}

	void remove(int v){
		if(s1.size() == s2.size()){
			if(v < *s2.begin()){
				sum1 -= v;
				s1.erase(s1.find(v));

				sum1 += *s2.begin(); 
				s1.insert(*s2.begin());
				
				sum2 -= *s2.begin(); 
				s2.erase(s2.begin());
			}
			else{
				sum2 -= v;
				s2.erase(s2.find(v));
			}
		}
		else{
			if(v <= *s1.rbegin()){
				sum1 -= v;
				s1.erase(s1.find(v));
			}
			else{
				sum2 -= v;
				s2.erase(s2.find(v));

				sum2 += *(--s1.end()) ;
				s2.insert( *(--s1.end()) );

				sum1 -= *(--s1.end()) ;
				s1.erase( --s1.end() );
			}
		}
	}

	ll dist(){
		return median()*s1.size()-sum1 + sum2 - median()*s2.size();
	}
};
two_set esq, dir;

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int k, n;
	cin >> k >> n;
	for(int i = 1; i <= n; i++){
		char za, zb; int a, b;
		cin >> za >> a >> zb >> b;
		if(a>b) swap(a, b);
		if(za==zb){
			ans += b-a;
		}
		else{
			ans++;
			inter.push_back({a, b});
		}
	}
	debug(ans)
	sort(inter.begin(), inter.end(), cmp);

	for(auto[L, R] : inter){
		dir.add(L);
		dir.add(R);

		debug(L);
		debug(R);
		debug(dir.median());
		debug(dir.dist());
	}
	debug(dir.median());

	ll best = ans+dir.dist();
	if(k == 1 || inter.empty()){
		cout << best << '\n';
		return 0;
	}

	for(auto[L, R] : inter){
		dir.remove(L);
		dir.remove(R);
		esq.add(L);
		esq.add(R);

		debug(dir.median());
		debug(dir.dist());
		debug(esq.median());
		debug(esq.dist());
		debug(' ');

		best = min(best, dir.dist()+esq.dist());
	}
	debug(best)
	cout << ans+best << '\n';
}

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