제출 #483386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483386		PixelCat	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	361 ms	13656 KiB

bridge

/*       code by the cute PixelCat owo       */
/*   as cute as nacho neko (aka. my wife)!   */
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL //__int128
#define double long double
using namespace std;
using LL=long long;
using uLL=unsigned long long;
using pii=pair<LL,LL>;

#define For(i,a,b)    for(int i=a;i<=b;i++)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define Forr(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)
#define LO(x) (x&(-x))

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(1000000007)
#define INF (int)(1000000000000000ll) //1e15
#define EPS (1e-6)

#ifdef NYAOWO
#include "debug.h"
inline void USACO(const string &s) { cerr<<"USACO: "<<s<<"\n"; }

#else
#define debug(...)
inline void timer(){}
inline void USACO(const string &s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

#endif

inline void NYA(){ ios::sync_with_stdio(false); cin.tie(0); }
inline int gcd(int a,int b) { return __gcd(a,b); }
inline int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p,const int &mod){
	int ans=1;
	while(p){
		if(p&1) ans=ans*b%mod;
		p/=2; b=b*b%mod;
	}
	return ans;
}
int fpow(int b,int p) { return fpow(b,p,MOD); }
template<typename T> inline void chmin(T &_a,const T &_b) { if(_b<_a) _a=_b; }
template<typename T> inline void chmax(T &_a,const T &_b) { if(_b>_a) _a=_b; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct DynamicMed{
	int sl,sh;
	multiset<int> lo,hi;
	void init(){
		lo.clear();
		hi.clear();
		sl=sh=0;
	}
	void bal(){
		if(sz(lo)>sz(hi)+1){
			int a=*lo.rbegin();
			sl-=a; sh+=a;
			hi.insert(a);
			lo.erase(lo.find(a));
		}
		if(sz(lo)<sz(hi)){
			int a=*hi.begin();
			sl+=a; sh-=a;
			hi.erase(hi.find(a));
			lo.insert(a);
		}
	}
	void insert(int k){
		if(sz(hi) && k>*hi.begin()){
			sh+=k;
			hi.insert(k);
		}else{
			sl+=k;
			lo.insert(k);
		}
		bal();
	}
	void remove(int k){
		if(sz(hi) && k>=*hi.begin()){
			sh-=k;
			hi.erase(hi.find(k));
		}else{
			sl-=k;
			lo.erase(lo.find(k));
		}
		bal();
	}
	int rape(){
		int ans=sh-sl;
		if(sz(lo)>sz(hi)) ans+=*lo.rbegin();
		return ans;
	}
	void fuck(){
		debug(sh,sl,hi,lo);
	}
}lo,li;

int32_t main(){
	NYA();
	//nyaacho >/////<
	// weird emojis credit to uglyfeng
	// OwO
	// OwQ
	// QwO
	// QwQ
	int k,n; cin>>k>>n;
	int add=0;
	vector<pii> v;
	For(i,1,n){
		char z1,z2;
		int p1,p2;
		cin>>z1>>p1>>z2>>p2;
		if(z1==z2){
			add+=abs(p1-p2);
		}else{
			add++;
			v.eb(p1,p2);
			li.insert(p1);
			li.insert(p2);
		}
	}
	sort(all(v),[](const pii &a,const pii &b){
		return a.F+a.S<b.F+b.S;
	});
	int ans=add+li.rape();
	if(k==1){
		cout<<ans<<"\n";
		return 0;
	}
	For(i,0,sz(v)-1){
		li.remove(v[i].F);
		li.remove(v[i].S);
		lo.insert(v[i].F);
		lo.insert(v[i].S);
		chmin(ans,add+lo.rape()+li.rape());
		debug(i,add,lo.rape(),li.rape());
		lo.fuck();
		li.fuck();
	}
	cout<<ans<<"\n";
	return 0;
}

// OwO
// UwU

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