제출 #1324229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324229		sh_qaxxorov_571	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	99 ms	8536 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;

struct Person {
    ll s, t;
};

// Mediana yordamida masofalarni hisoblash uchun Priority Queues usuli
struct MedianFinder {
    priority_queue<ll> left; // Max-heap
    priority_queue<ll, vector<ll>, greater<ll>> right; // Min-heap
    ll leftSum = 0, rightSum = 0;

    void add(ll val) {
        if (left.empty() || val <= left.top()) {
            left.push(val); leftSum += val;
        } else {
            right.push(val); rightSum += val;
        }
        // Balanslash
        if (left.size() > right.size() + 1) {
            ll tmp = left.top(); left.pop(); leftSum -= tmp;
            right.push(tmp); rightSum += tmp;
        } else if (right.size() > left.size()) {
            ll tmp = right.top(); right.pop(); rightSum -= tmp;
            left.push(tmp); leftSum += tmp;
        }
    }

    ll getCost() {
        ll median = left.top();
        return (median * (ll)left.size() - leftSum) + (rightSum - median * (ll)right.size());
    }
};

int main() {
    int K, N;
    cin >> K >> N;

    ll baseDist = 0;
    vector<Person> crossers;

    for (int i = 0; i < N; i++) {
        char pZ, qZ; ll s, t;
        cin >> pZ >> s >> qZ >> t;
        if (pZ == qZ) {
            baseDist += abs(s - t);
        } else {
            baseDist += 1; // Daryoni o'tish
            crossers.push_back({min(s, t), max(s, t)});
        }
    }

    if (crossers.empty()) {
        cout << baseDist << endl; return 0;
    }

    // K=1 holati
    sort(crossers.begin(), crossers.end(), [](Person a, Person b) {
        return a.s + a.t < b.s + b.t;
    });

    int M = crossers.size();
    if (K == 1) {
        vector<ll> allCoords;
        for (auto p : crossers) { allCoords.push_back(p.s); allCoords.push_back(p.t); }
        sort(allCoords.begin(), allCoords.end());
        ll median = allCoords[M];
        ll addCost = 0;
        for (ll c : allCoords) addCost += abs(c - median);
        cout << baseDist + addCost << endl;
    } else {
        // K=2 holati uchun Prefiks va Suffiks medianalar
        vector<ll> pref(M), suff(M);
        MedianFinder mfLeft, mfRight;

        for (int i = 0; i < M; i++) {
            mfLeft.add(crossers[i].s); mfLeft.add(crossers[i].t);
            pref[i] = mfLeft.getCost();
        }
        for (int i = M - 1; i >= 0; i--) {
            mfRight.add(crossers[i].s); mfRight.add(crossers[i].t);
            suff[i] = mfRight.getCost();
        }

        ll minAddCost = pref[M - 1];
        for (int i = 0; i < M - 1; i++) {
            minAddCost = min(minAddCost, pref[i] + suff[i + 1]);
        }
        cout << baseDist + minAddCost << endl;
    }

    return 0;
}

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