Submission #577931

#	Time	Username	Problem	Language	Result	Execution time	Memory
577931		MohamedFaresNebili	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	105 ms	6644 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define int ll

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        bool cmp(ii A, ii B) {
            return A.ff + A.ss < B.ff + B.ss;
        }

        int K, N, A, B, Pr[100001];
        priority_queue<int> L, R;
        vector<ii> arr;
        void solve(int V) {
            int md = L.size() ? L.top() : 1e9 + 7;
            if(V <= md) {
                L.push(V); A += V;
            }
            else {
                R.push(-V); B += V;
            }
            if(L.size() > R.size() + 1) {
                V = L.top(); L.pop();
                R.push(-V); A -= V; B += V;
            }
            else if(L.size() < R.size()) {
                V = -R.top(); R.pop();
                L.push(V); A += V; B -= V;
            }
        }

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> K >> N; int res = 0, curr = 0;
            for(int l = 0; l < N; l++) {
                char P, Q; int S, T;
                cin >> P >> S >> Q >> T;
                if(P == Q) {
                    curr += abs(T - S);
                    continue;
                }
                arr.pb({S, T});
            }
            sort(arr.begin(), arr.end(), cmp);
            N = arr.size(); curr += N;
            for(int l = 0; l < N; l++) {
                solve(arr[l].ff);
                solve(arr[l].ss);
                Pr[l] = B - A;
            }
            res = Pr[N - 1];
            if(K == 2) {
                A = B = 0;
                while(!L.empty()) L.pop();
                while(!R.empty()) R.pop();
                for(int l = N - 1; l >= 0; l--) {
                    res = min(res, B - A + Pr[l]);
                    solve(arr[l].ff);
                    solve(arr[l].ss);
                }
            }
            cout << res + curr << "\n";
            return 0;
        }

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