Submission #728416

#	Time	Username	Problem	Language	Result	Execution time	Memory
728416		becaido	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	68 ms	5792 KiB

bridge

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

int n, k;
int a[2 * SIZE];
ll ans, sum[SIZE];
pair<int, int> p[SIZE];

ll lsum, rsum;
int lcnt, rcnt, mid;
priority_queue<int> lpq;
priority_queue<int, vector<int>, greater<int>> rpq;

void Add (int x) {
    if (lpq.empty() || x <= lpq.top()) {
        lcnt++;
        lsum += x;
        lpq.push (x);
    } else {
        rcnt++;
        rsum += x;
        rpq.push (x);
    }
    while (rpq.size() > lpq.size()) {
        int y = rpq.top();
        rpq.pop();
        rcnt--;
        rsum -= y;
        lpq.push (y);
        lcnt++;
        lsum += y;
    }
    while (lpq.size() > rpq.size() + 1) {
        int y = lpq.top();
        lpq.pop();
        lcnt--;
        lsum -= y;
        rpq.push (y);
        rcnt++;
        rsum += y;
    }
    mid = lpq.top();
}

void solve() {
    cin >> k >> n;
    if (k == 1) {
        int siz = 0;
        FOR (i, 1, n) {
            char cx, cy;
            int x, y;
            cin >> cx >> x >> cy >> y;
            if (cx == cy) ans += abs (x - y);
            else {
                ans++;
                a[++siz] = x;
                a[++siz] = y;
            }
        }
        n = siz;
        nth_element (a + 1, a + (n + 1) / 2, a + n + 1);
        mid = a[(n + 1) / 2];
        FOR (i, 1, n) ans += abs (a[i] - mid);
        cout << ans << '\n';
        return;
    }
    int siz = 0;
    FOR (i, 1, n) {
        char cx, cy;
        int x, y;
        cin >> cx >> x >> cy >> y;
        if (cx == cy) ans += abs (x - y);
        else {
            ans++;
            p[++siz] = {x, y};
        }
    }
    n = siz;
    sort (p + 1, p + n + 1, [] (auto p1, auto p2) {
        return p1.F + p1.S < p2.F + p2.S;
    });
    FOR (i, 1, n) {
        auto [x, y] = p[i];
        Add (x), Add (y);
        sum[i] += (lcnt - rcnt) * mid - lsum + rsum;
    }
    lcnt = rcnt = 0;
    lsum = rsum = 0;
    lpq = {}, rpq = {};
    for (int i = n; i >= 1; i--) {
        auto [x, y] = p[i];
        Add (x), Add (y);
        sum[i - 1] += (lcnt - rcnt) * mid - lsum + rsum;
    }
    cout << ans + *min_element (sum, sum + n + 1) << '\n';
}

int main() {
    Waimai;
    solve();
}

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