제출 #882688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882688		Kel_Mahmut	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	181 ms	9776 KiB

bridge

#include<bits/stdc++.h>
#define all(aa) aa.begin(), aa.end()
#define endl ("\n")
#define pb push_back
typedef long long ll;
const int maxn = 1e5 + 5;
using namespace std;

int n, k;
vector<pair<ll, ll>> v;
vector<ll> u;
multiset<pair<ll, ll>> nxt, in;
multiset<pair<ll, pair<ll, ll>>> vis; // vis r'ye gore artan come l'ye gore artan
ll lft, rgt, lst;
ll ans = LONG_LONG_MAX, cur, rem;
bool ok;

ll dst(pair<ll, ll> p, ll ind){
	if(p.first <= ind && ind <= p.second) return 0;
	return 2*min(abs(p.first - ind), abs(p.second - ind));
}

int main(){
	cin >> k >> n;
	for(int i = 0; i < n; i++){
		char c1, c2;
		int a, b;
		cin >> c1 >> a >> c2 >> b;
		if(b > a) swap(a, b);
		rem+=a-b;
		if(c1!=c2){
			ok = 1;
			++rem;
			v.pb({b, a});
			u.pb(a), u.pb(b);
		}
	}
	rgt = n = v.size();
	sort(all(u));
	sort(all(v));
	if(!ok){
		cout << rem << endl;
		exit(0);
	}
	
	if(k == 2){
	for(int l = 0; l < 2*n; l++){
		cur = 0;
		lft = rgt = 0, lst = u[l];
		for(int i = 0; i < n; i++){
			cur += dst(v[i], u[l]);
			if(u[l] < v[i].first){
				nxt.insert(v[i]);
				rgt++;
			}
		}

		for(int r = l; r < 2*n; r++){
			cur += lft*2*(u[r] - lst) - rgt*2*(u[r] - lst);

			while(!nxt.empty() && (*nxt.begin()).first == u[r]){
				pair<ll, ll> p = *nxt.begin();
				in.insert({p.second, p.first});
				nxt.erase(nxt.begin());
				rgt--;
			}

			while(!in.empty() && (*in.begin()).first == u[r]){
				pair<ll, ll> p = *in.begin();
				in.erase(in.begin());
				pair<ll, ll> fix = {p.second, p.first};
				vis.insert({dst(fix, u[l]) - dst(fix, u[r]), fix});
				lft++;
			}
			while(!vis.empty() && dst((*vis.begin()).second, u[r]) > dst((*vis.begin()).second, u[l]) ){
				pair<ll, ll> p = (*vis.begin()).second;
				lft--;
				vis.erase(vis.begin());
				cur += dst(p, u[l]) - dst(p, u[r]);
			}
			ans = min(ans, cur);
			lst = u[r];
		}
		vis.clear();
		nxt.clear();
		in.clear();	
	}
	assert(ans!=LONG_LONG_MAX);
	cout << ans + rem << endl;
	} else{
		cur = rem;
		rgt = n, lst = lft = 0;
		multiset<pair<ll, ll>> come;
		multiset<ll> vs;
		for(int i = 0; i < n; i++){
			come.insert(v[i]);
			cur+=2*v[i].first;
		}
		ans = cur;
		for(int i = 0; i < 2*n; i++){
			cur += lft*2*(u[i] - lst) - rgt*2*(u[i] - lst);
			while(!come.empty() && (*come.begin()).first == u[i]){
				pair<ll, ll> p = *come.begin();
				vs.insert({p.second});
				come.erase(come.find(p));
				rgt--;
			} 
			while(!vs.empty() && *vs.begin() == u[i]){
				lft++;
				vs.erase(vs.begin());
			}
			ans = min(ans, cur);
			lst = u[i];
		}
		cout << ans << endl;
	}
	

	
}

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