Submission #1276187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276187		vk3601h	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	66 ms	6156 KiB

bridge

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int bridge_num, people_num;
    cin >> bridge_num >> people_num;

    long long ans = 0;

    vector<pair<long long, long long>> intervals;
    for (int i = 0; i < people_num; i++){
        char P, Q;
        long long S, T;
        cin >> P >> S >> Q >> T;
        if (P == Q) ans += abs(S - T);
        else intervals.push_back({S, T});
    }
    sort(intervals.begin(), intervals.end(),
         [](const pair<long long, long long> &a, const pair<long long, long long> &b)
         {return a.first + a.second < b.first + b.second;});
    people_num = intervals.size();
    ans += people_num;

    long long low_sum = 0, high_sum = 0;
    priority_queue<long long> low;
    priority_queue<long long, vector<long long>, greater<long long>> high;
    auto insert = [&](long long val){
        long long median = (low.empty() ? (long long)1e9 + 1 : low.top());
        if (val <= median){
            low_sum += val;
            low.push(val);
        }
        else {
            high_sum += val;
            high.push(val);
        }

        if ((int)low.size() < (int)high.size()){
            long long moving = high.top();
            low_sum += moving;
            high_sum -= moving;
            low.push(moving);
            high.pop();
        }
        else if ((int)low.size() > (int)high.size() + 1){
            long long moving = low.top();
            low_sum -= moving;
            high_sum += moving;
            high.push(moving);
            low.pop();
        }
    };

    vector<long long> pref(people_num + 1);
    pref[0] = 0;
    for (int i = 0; i < people_num; i++){
        insert(intervals[i].first);
        insert(intervals[i].second);
        pref[i + 1] = high_sum - low_sum;
    }
    long long oppo_ans = pref[people_num];

    if (bridge_num == 2){
        while (!low.empty()) low.pop();
        while (!high.empty()) high.pop();
        low_sum = high_sum = 0;

        for (int i = people_num - 1; i >= 0; i--){
            insert(intervals[i].first);
            insert(intervals[i].second);
            oppo_ans = min(oppo_ans, high_sum - low_sum + pref[i]);
        }
    }

    cout << ans + oppo_ans;
    return 0;
}

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