oj.uz

Submission #1094815

# Submission time Handle Problem Language Result Execution time Memory
1094815 2024-09-30T15:48:00 Z Octa_pe_info Palembang Bridges (APIO15_bridge) C++14
0 / 100
 1 ms 348 KB 
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

multiset<int> st, dr;
long long ssum = 0, dsum = 0;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first + a.second < b.first + b.second;
}

void adauga(int nr) {
    int mid = st.empty() ? 10000001 : *st.rbegin();

    if (nr <= mid) {
        st.insert(nr);
        ssum += nr;
    } else {
        dr.insert(nr);
        dsum += nr;
    }

    // Balancing the sets
    if (dr.size() + 1 < st.size()) {
        int auxs = *st.rbegin();
        st.erase(st.find(auxs));
        dr.insert(auxs);
        ssum -= auxs;
        dsum += auxs;
    } else if (st.size() < dr.size()) {
        int auxs = *dr.begin();
        dr.erase(dr.find(auxs));
        st.insert(auxs);
        dsum -= auxs;
        ssum += auxs;
    }
}

int main() {
    int n, k;
    cin >> k >> n;

    vector<pair<int, int>> poz;
    long long ans = 0, fel = 0;

    for (int i = 1; i <= n; i++) {
        int a, b;
        char c, cc;
        cin >> c >> a >> cc >> b;

        if (c == cc)
            fel += abs(a - b);  // If both locations are on the same side
        else
            poz.push_back({a, b});  // If they are on opposite sides, add to the positions
    }

    sort(poz.begin(), poz.end(), cmp);
    fel += poz.size();  // Counting the river crossings

    vector<long long> api(poz.size());

    // First pass to compute differences
    for (int i = 0; i < poz.size(); i++) {
        adauga(poz[i].first);
        adauga(poz[i].second);
        api[i] = dsum - ssum;
    }

    ans = api[poz.size() - 1];  // The largest difference at the end

    if (k == 2) {
        // Clear the multisets for the second pass
        st.clear();
        dr.clear();
        ssum = dsum = 0;

        for (int i = poz.size() - 1; i >= 0; i--) {
            adauga(poz[i].first);
            adauga(poz[i].second);
            
            if (i > 0) {  // Avoid accessing api[-1]
                ans = min(ans, dsum - ssum + api[i - 1]);
            }
        }
    }

    cout << ans + fel;

    return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < poz.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -