Submission #932175

#	Time	Username	Problem	Language	Result	Execution time	Memory
932175		ShadowShark	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	77 ms	6088 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 5;
struct type {
    char c1; int x1;
    char c2; int x2;
} person[maxN];

bool cmp(type a, type b) {
    return (a.x1 + a.x2) < (b.x1 + b.x2);
}

int k, n;

long long ans = 0;

void subtask1() {
    vector<int> val;
    for (int i = 1; i <= n; i++) {
        val.push_back(person[i].x1);
        val.push_back(person[i].x2);
    }
    sort(val.begin(), val.end());
    int median = val[int(val.size() - 1) / 2];
    //cout << median << '\n';

    for (int i = 1; i <= n; i++)
        ans += abs(person[i].x1 - median) + abs(person[i].x2 - median) + 1;

    cout << ans;
    return ;
}

void subtask2() {
    sort(person + 1, person + n + 1, cmp);

    long long res = 1e18;

    vector<int> val1, val2;
    for (int i = 1; i <= n - 1; i++) {
        val1.clear();
        val2.clear();

        for (int j = 1; j <= i; j++) {
            val1.push_back(person[j].x1);
            val1.push_back(person[j].x2);
        }

        for (int j = i + 1; j <= n; j++) {
            val2.push_back(person[j].x1);
            val2.push_back(person[j].x2);
        }

        sort(val1.begin(), val1.end());
        sort(val2.begin(), val2.end());

        long long cal = 0;
        int med1 = val1[int(val1.size() - 1) / 2], med2 = val2[int(val2.size() - 1) / 2];

        for (auto v: val1)
            cal = cal + abs(v - med1);

        for (auto v: val2)
            cal = cal + abs(v - med2);

        res = min(res, cal);
    }

    cout << res + ans + n;
    return ;
}

priority_queue<int> lhs;
priority_queue<int, vector<int>, greater<int>> rhs;

long long pre[maxN], lsum = 0, rsum = 0;

void add(int x) {
    int median = (lhs.empty() ? 1000000007 : lhs.top());
    if (x <= median) {
        lhs.push(x);
        lsum += x;
    }
    else {
        rhs.push(x);
        rsum += x;
    }

    if (lhs.size() > rhs.size() + 1) {
        rhs.push(lhs.top());
        rsum += lhs.top();

        lsum -= lhs.top();
        lhs.pop();
    }

    else if (lhs.size() < rhs.size()) {
        lhs.push(rhs.top());
        lsum += rhs.top();

        rsum -= rhs.top();
        rhs.pop();
    }
}

void subtask3() {
    sort(person + 1, person + n + 1, cmp);

    for (int i = 1; i <= n; i++) {
        add(person[i].x1);
        add(person[i].x2);

        pre[i] = rsum - lsum;
    }

    while (!lhs.empty()) lhs.pop();
    while (!rhs.empty()) rhs.pop();

    lsum = 0; rsum = 0;
    long long res = pre[n];

    for (int i = n; i >= 1; i--) {
        add(person[i].x1);
        add(person[i].x2);

        res = min(res, pre[i - 1] + rsum - lsum);
    }

    cout << res + ans + n;
    return ;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> k >> n;

    for (int i = 1; i <= n; i++) {
        char c1, c2;
        int x1, x2;
        cin >> c1 >> x1 >> c2 >> x2;
        if (c1 == c2) {
            ans = ans + abs(x1 - x2);
            n--;
            i--;
            continue;
        }
        person[i] = {c1, x1, c2, x2};
    }

    if (n == 0) {
        cout << ans;
        return 0;
    }

    if (k == 1) subtask1();
        else if (n <= 1000) subtask2();
            else subtask3();

    return 0;
}

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