Submission #932111

#	Time	Username	Problem	Language	Result	Execution time	Memory
932111		ShadowShark	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	31 ms	3188 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];
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 ;
}

multiset<int> left1, right1, left2, right2;
long long sum_left1 = 0, sum_right1 = 0, sum_left2 = 0, sum_right2 = 0;

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

void add_to_the_second(int i) {
    right2.insert(person[i].x1);
    right2.insert(person[i].x2);

    sum_right2 += person[i].x1;
    sum_right2 += person[i].x2;

    int exchange = *right2.begin();

    left2.insert(exchange);
    right2.erase(right2.find(exchange));
    sum_left2 += exchange;
    sum_right2 -= exchange;
}

void delete_from_the_second(int i) {
    int x1 = person[i].x1, x2 = person[i].x2;

    int med_right = *right2.begin();

    /// Erase x1 from the second set
    if (x1 < med_right || right2.size() == 0) {
        left2.erase(left2.find(x1));
        sum_left2 -= x1;
    }
    else {
        right2.erase(right2.find(x1));
        sum_right2 -= x1;
    }

    med_right = (right2.size() > 0 ? *right2.begin() : 1e9 + 7);
    /// Erase x2 from the second set
    if (x2 < med_right) {
        left2.erase(left2.find(x2));
        sum_left2 -= x2;
    }
    else {
        right2.erase(right2.find(x2));
        sum_right2 -= x1;
    }

    if (left2.size() > right2.size()) {
        auto it = left2.end(); it--;
        int exchange = *it;
        left2.erase(it);
        right2.insert(exchange);
        sum_left2 -= exchange;
        sum_right2 += exchange;
    }
    else if (left2.size() < right2.size()) {
        auto it = right2.begin();
        int exchange = *it;
        right2.erase(it);
        left2.insert(exchange);
        sum_left2 += exchange;
        sum_right2 -= exchange;
    }
}

void add_to_the_first(int i) {
    int x1 = person[i].x1, x2 = person[i].x2;

    right1.insert(x1);
    right1.insert(x2);

    sum_right1 += x1;
    sum_right1 += x2;

    int exchange = *right1.begin();
    right1.erase(right1.find(exchange));
    left1.insert(exchange);

    sum_right1 -= exchange;
    sum_left1 += exchange;
}

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

    for (int i = 1; i <= n; i++)
        add_to_the_second(i);

    long long res = 1e18;

    for (int i = 1; i <= n - 1; i++) {
        delete_from_the_second(i);
        add_to_the_first(i);

        int median_first = *right1.begin();
        int median_second = *right2.begin();
        long long cal = (1LL * median_first * i - sum_left1) + (sum_right1 - 1LL * median_first * (1LL * i));
        cal = cal + (1LL * median_second * (1LL * (n - i)) - sum_left2) + (sum_right2 - 1LL * median_second * (1LL * (n - i)));
        res = min(res, cal);
    }

    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 (k == 1) subtask1();
        else subtask2();

    return 0;
}

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