Submission #882926

#	Time	Username	Problem	Language	Result	Execution time	Memory
882926		NotLinux	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2094 ms	10984 KiB

bridge

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// PUT IT BEFORE THE INCLUDE
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 7;
struct ONLINE_MEDIAN{
	long long sum1 = 0 , sum2 = 0;
	int sz = 0;
	multiset < int > s1,s2;
	inline void insert(int x){
		sum2 += x;
		s2.insert(x);
		sz++;
		while(s1.size() < ((sz+1)/2)){
			sum1 += *s2.begin();
			s1.insert(*s2.begin());
			sum2 -= *s2.begin();
			s2.erase(s2.begin());
		}
		while(s2.size() and *(--s1.end()) > *(s2.begin())){
			sum2 += *(--s1.end());
			s2.insert(*(--s1.end()));
			sum1 -= *(--s1.end());
			s1.erase(--s1.end());
			sum1 += *s2.begin();
			s1.insert(*s2.begin()),
			sum2 -= *s2.begin();
			s2.erase(s2.begin());
		}
	}
	inline void erase(int x){
		if(s1.count(x)){
			sum1 -= x;
			s1.erase(s1.find(x));
		}
		else {
			sum2 -= x;
			s2.erase(s2.find(x));
		}
		sz--;
		while(s1.size() > ((sz+1)/2)){
			sum2 += *(--s1.end());
			s2.insert(*(--s1.end())),
			sum1 -= *(--s1.end());
			s1.erase(--s1.end());
		}
		while(s1.size() < ((sz+1)/2)){
			sum1 += *(s2.begin());
			s1.insert(*s2.begin());
			sum2 -= *(s2.begin());
			s2.erase(s2.begin());
		}
		while(s2.size() and *(--s1.end()) > *(s2.begin())){
			sum2 += *(--s1.end());
			s2.insert(*(--s1.end()));
			sum1 -= *(--s1.end());
			s1.erase(--s1.end());
			sum1 += *s2.begin();
			s1.insert(*s2.begin()),
			sum2 -= *s2.begin();
			s2.erase(s2.begin());
		}
	}
	inline int get_median(){
		if(s1.empty())return 0;
		return *(--s1.end());
	}
	inline long long get_ans(){
		int medi = get_median();
		return (1ll * medi * s1.size() - sum1) + (sum2 - 1ll * medi * s2.size());
	}
	inline void debug(){
		cout << "set : ";
		for(auto itr : s1)cout << itr << " ";
		cout << "|";
		for(auto itr : s2)cout << itr << " ";
	}
};
bool cmp(array < int , 3 > const& a , array < int , 3 > const& b){
	return a[0] < b[0];
}
void solve(){
	int k,n;
	long long ans0 = 0;
	cin >> k >> n;
	vector < array < int , 3 > > v2;
	for(int i = 0;i<n;i++){
		char c1,c2;
		int p1,p2;
		cin >> c1 >> p1 >> c2 >> p2;
		if(c1 == c2){
			ans0 += abs(p1 - p2);
		}
		else{
			v2.push_back({p1 + p2 , p1 , p2});
		}
	}
	sort(v2.begin() , v2.end() , cmp);
	ONLINE_MEDIAN med1 , med2;
	for(auto itr : v2){
		med2.insert(itr[1]);
		med2.insert(itr[2]);
	}
	long long ans1 = inf;
	if(k == 1){
		ans1 = med2.get_ans();
	}
	else{
		for(auto itr : v2){
			med2.erase(itr[1]);
			med2.erase(itr[2]);
			med1.insert(itr[1]);
			med1.insert(itr[2]);
			ans1 = min(ans1 , med1.get_ans() + med2.get_ans());
		}
	}
	cout << ans0 + (ans1 == inf ? 0ll : ans1) + v2.size() << '\n';
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Compilation message (stderr)

bridge.cpp: In member function 'void ONLINE_MEDIAN::insert(int)':
bridge.cpp:15:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |   while(s1.size() < ((sz+1)/2)){
      |         ~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp: In member function 'void ONLINE_MEDIAN::erase(int)':
bridge.cpp:42:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |   while(s1.size() > ((sz+1)/2)){
      |         ~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp:48:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |   while(s1.size() < ((sz+1)/2)){
      |         ~~~~~~~~~~^~~~~~~~~~~~

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