Submission #39865

#	Time	Username	Problem	Language	Result	Execution time	Memory
39865		nickyrio	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	289 ms	48804 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];
pp BIT[N];
vector<long long> ranking;
vector<pp> e;

void Up(int u, long long val) {
    for (; u <= m; u += u & -u) {
        BIT[u].first += val;
        BIT[u].second++;
    }
}

pp Get(int u) {
    pp ans = pp(0, 0);
    for (; u > 0; u -= u & -u) {
        ans.first += BIT[u].first;
        ans.second += BIT[u].second;
    }
    return ans;
}

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
    FOR(i, 1, m) BIT[i] = pp(0, 0);// pair<Sum, counter>
    long long total = 0;
    REP(i, n) {
        int pos = lower_bound(ranking.begin(), ranking.end(), x1[e[i].second]) - ranking.begin() + 1;
        Up(pos, x1[e[i].second]);
            pos = lower_bound(ranking.begin(), ranking.end(), x2[e[i].second]) - ranking.begin() + 1;
        Up(pos, x2[e[i].second]);
        total += e[i].first;

        BottomMax.push(x1[e[i].second]);
        BottomMax.push(x2[e[i].second]);
        while (BottomMax.size() - TopMin.size() > 1) {
            TopMin.push(BottomMax.top());
            BottomMax.pop();
            if (!BottomMax.empty() && TopMin.top() < BottomMax.top()) {
                BottomMax.push(TopMin.top());
                TopMin.pop();
            }
        }
        int posMed = lower_bound(ranking.begin(), ranking.end(), BottomMax.top()) - ranking.begin() + 1;
        pp lowerMed = Get(posMed);
        Right[i] = ranking[posMed - 1] * lowerMed.second - lowerMed.first
             + total - lowerMed.first - ranking[posMed - 1] * (2 * i + 2 - lowerMed.second);
    }
}

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