oj.uz

Submission #932109

# Submission time Handle Problem Language Result Execution time Memory
932109 2024-02-23T02:50:57 Z vjudge1 Palembang Bridges (APIO15_bridge) C++17
22 / 100
 37 ms 5356 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 480 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 616 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 484 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 15 ms 4180 KB Output is correct
13 Correct 37 ms 5356 KB Output is correct
14 Correct 23 ms 4060 KB Output is correct
15 Correct 19 ms 3296 KB Output is correct
16 Correct 21 ms 4608 KB Output is correct
17 Correct 21 ms 5340 KB Output is correct
18 Correct 26 ms 4816 KB Output is correct
19 Correct 31 ms 5340 KB Output is correct
20 Correct 21 ms 5080 KB Output is correct
21 Correct 28 ms 5116 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -