Submission #39866

#	Time	Username	Problem	Language	Result	Execution time	Memory
39866		nickyrio	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	156 ms	33172 KiB

bridge

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b ; --i)
#define REP(i, a) for (int i = 0, _a = (a); i < _a; ++i)
#define pp pair<long long, long long>
#define bit(S, i) (((S) >> i) & 1)
#define next __next
#define prev __prev
#define N 1000030

using namespace std;
int n, m, x1[N], x2[N];
vector<long long> ranking;
vector<pp> e;

priority_queue<long long> BottomMax;
priority_queue<long long, vector<long long>, greater<long long> > TopMin;
long long Left[N], Right[N];

void Solve() {
    while (!BottomMax.empty()) BottomMax.pop();
    while (!TopMin.empty()) TopMin.pop();
    // Median is top of BottomMax
    long long Low = 0, High = 0;
    REP(i, n) {
        BottomMax.push(x1[e[i].second]);
        BottomMax.push(x2[e[i].second]);
        Low += x1[e[i].second];
        Low += x2[e[i].second];
        while (BottomMax.size() - TopMin.size() > 1) {
            TopMin.push(BottomMax.top());
            Low -= BottomMax.top();
            High += BottomMax.top();
            BottomMax.pop();
            if (!BottomMax.empty() && TopMin.top() < BottomMax.top()) {
                BottomMax.push(TopMin.top());
                Low += TopMin.top();
                High -= TopMin.top();
                TopMin.pop();
            }
        }
        Right[i] = BottomMax.top() * BottomMax.size() - Low
             + High - BottomMax.top() * TopMin.size();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int k;
    cin >> k >> n;
    long long init = 0;
    FOR(i, 1, n) {
        char label1, label2;
        cin >> label1 >> x1[i] >> label2 >> x2[i];
        if (x1[i] > x2[i]) swap(x1[i], x2[i]);
        if (label1 == label2) {
            init += x2[i] - x1[i];
        }
        else {
            e.push_back(pp(x1[i] + x2[i], i));
            ranking.push_back(x1[i]);
            ranking.push_back(x2[i]);
            init++;
        }
    }
    //Initialization
    sort(ranking.begin(), ranking.end());
    ranking.resize(unique(ranking.begin(), ranking.end()) - ranking.begin());
    n = e.size();
    sort(e.begin(), e.end());
    m = ranking.size();
    // Cal median from Left to Right
    Solve();
    REP(i, n) Left[i] = Right[i];
    // Cal median from Right to Left
    reverse(e.begin(), e.end());
    Solve();
    reverse(Right, Right + n);
    if (k == 1) cout << Left[n - 1] + init;
    else {
        long long best = Right[0];
        REP(i, n - 1) best = min(best, Left[i] + Right[i + 1]);
        cout << best + init;
    }
}

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