Submission #1094815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094815		Octa_pe_info	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	348 KiB

bridge

#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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37