제출 #1181278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181278		peteza	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	96 ms	5360 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, ll> cans;
ll a1[200005], a2[200005];

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;
    vector<pair<int, pair<int, int>>> vecs;
	while(q--) {
		cin >> A >> a >> B >> b;
		if(a>b) swap(a, b);
		if(A==B) {
			ans += b-a;
		} else {
			ans++;
            vecs.emplace_back(a + b, make_pair(a, b));
		}
	}
    if(vecs.empty()) {cout << ans; return 0;}
    sort(vecs.begin(), vecs.end());
    for(int i=0;i<vecs.size();i++) {
        upd(vecs[i].second.first);
        upd(vecs[i].second.second);
        a1[i] = sum;
    }
    if(k == 1) {cout << sum + ans; return 0;}
    while(!l.empty()) l.pop(); while(!r.empty()) r.pop();
    sum = 0;
    ll cmin = LLONG_MAX;
    for(int i=vecs.size()-1;i>=0;i--) {
        cmin = min(cmin, sum + a1[i]);
        upd(vecs[i].second.first);
        upd(vecs[i].second.second);
    }
    cout << cmin + ans;
}

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