Submission #866291

#	Time	Username	Problem	Language	Result	Execution time	Memory
866291		Dec0Dedd	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	130 ms	13508 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int N = 1e5+10;
const ll INF = 1e18;

ll a[N], b[N], n, k;

struct Median {
    priority_queue<ll> lw;
    priority_queue<ll, vector<ll>, greater<ll>> up;
    ll slw, sup;

    Median(): slw(0), sup(0) {}

    void add(int x) {
        if (!lw.empty() && lw.top() < x) up.push(x), sup+=x;
        else lw.push(x), slw+=x;

        while (up.size() > lw.size()) {
            sup-=up.top(), slw+=up.top();
            lw.push(up.top()), up.pop();
        }

        while (lw.size() > up.size()+1) {
            slw-=lw.top(), sup+=lw.top();
            up.push(lw.top()), lw.pop();
        }
    }

    ll que() {
        if (lw.empty()) return 0;
        ll vl=lw.top();
        return (vl*lw.size()-slw)+(sup-vl*up.size());
    }
};

int main() {
    cin>>k>>n;

    ll ans=0;
    vector<pii> v;
    for (int i=1; i<=n; ++i) {
        string p, s;
        cin>>p>>a[i]>>s>>b[i];

        if (p == s) {
            ans+=abs(a[i]-b[i]);
            continue;
        } ++ans;
        if (a[i] > b[i]) swap(a[i], b[i]);
        v.push_back({a[i]+b[i], i});
    } sort(v.begin(), v.end());

    if (v.empty()) {
        cout<<ans<<"\n";
        return 0;
    }

    // k = 1
    Median med;
    for (auto u : v)  med.add(a[u.second]), med.add(b[u.second]);
    ll ovl=med.que();

    // k = 2
    if (k == 2) {
        ll p[n+1]={}, suf[n+1]={}, sz=v.size();

        Median lf, rf;
        for (int j=0; j<sz; ++j) {
            lf.add(a[v[j].second]), lf.add(b[v[j].second]);
            p[j]=lf.que();
        }
        
        for (int j=sz-1; j>=0; --j) {
            rf.add(a[v[j].second]), rf.add(b[v[j].second]);
            suf[j]=rf.que();
        }

        ll g=INF;
        for (int j=0; j+1<sz; ++j) g=min(g, p[j]+suf[j+1]);
        ans+=min(ovl, g);
    } else ans+=ovl;
    cout<<ans<<"\n";
}

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