제출 #1180996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180996		peteza	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	153 ms	19632 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int k, q, a, b;
char A, B;
ll sum=0, ans=0;

priority_queue<int> l;
priority_queue<int, vector<int>, greater<int>> r;
map<int, vector<int>> mp;
map<int, ll> cans;

void upd(int pos) {
	if(l.empty()) {
		l.push(pos); r.push(pos);
		return;
	}
	if(pos < l.top()) {
		sum += l.top()-pos;
		l.push(pos);
		l.push(pos);
		r.push(l.top());
		l.pop();
	} else if(pos > r.top()) {
		sum += pos-r.top();
		r.push(pos);
		r.push(pos);
		l.push(r.top());
		r.pop();
	} else {
		l.push(pos); r.push(pos);
	}
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> k >> q;
	while(q--) {
		cin >> A >> a >> B >> b;
		if(a>b) swap(a, b);
		if(A==B) {
			ans += b-a;
		} else {
			ans++;
			mp[a].push_back(b);
		}
	}
	ll minminmin = 0;
	vector<int> revmap;
	for(auto &e:mp) {
		revmap.push_back(e.first);
		for(auto &E:e.second) {
			upd(e.first);
			upd(E);
		}
		cans[e.first] = sum;
		minminmin = sum;
	}
	reverse(revmap.begin(), revmap.end());
	sum=0;
	while(!l.empty()) l.pop();
	while(!r.empty()) r.pop();
	for(auto &e:revmap) {
		auto &vec = mp[e];
		if(k==2) minminmin = min(minminmin, cans[e]+sum);
		for(auto &E:vec) {
			upd(e);
			upd(E);
		}
	}
	cout << ans+minminmin;
}

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