Submission #1148848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148848		alir3za_zar3	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	221 ms	12056 KiB

bridge

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define     int     long long

struct median
{
    multiset<int> l,r;
    int szl=0 , szr=0;
    int sl=0 , sr=0;
    void update ()
    {
        while (szl - szr > 1)
        {
            int v = *l.rbegin();
            l.erase(l.lower_bound(v));
            r.insert(v);
            szl--; szr++;
            sl -= v; sr += v;
        }
        while (!r.empty() and szr > szl)
        {
            int v = *r.begin();
            r.erase(r.lower_bound(v));
            l.insert(v);
            szr--; szl++;
            sr -= v; sl += v;
        }
    }
    int ouT ()
    {
        if (l.empty()) return 0;
        int med = *l.rbegin();
        int out = szl*med - sl;
        out += sr - szr*med;
        return out;
    }
    void insert (int v)
    {
        int med = (l.empty() ? 0:(*l.rbegin()));
        if (v > med)
            r.insert(v) , szr++ , sr+=v;
        else
            l.insert(v) , szl++ , sl+=v;
        update();
    }
    void erase (int v)
    {
        int med = *l.rbegin();
        if (v > med)
            r.erase(r.lower_bound(v)) , szr-- , sr-=v;
        else
            l.erase(l.lower_bound(v)) , szl-- , sl-=v;
        update();
    }
} l,r;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);

	int k,n; cin >> k >> n;
    int sv = n;
    vector<tuple<int,int,int>> q;
    for (int i=1; i<=n; i++)
    {
        char P,Q; int S,T;
        cin >> P >> S >> Q >> T;
        if (P == Q) 
            sv += abs(T - S) - 1;
        else 
        {
            q.push_back({S+T , S , T});
            l.insert(S);   l.insert(T);
        }
    }
    int out = l.ouT()+sv , o;
    if (k == 1)
    {
        cout << out << '\n';
        return 0;
    }
    sort(q.begin(),q.end());
    for (auto [sum,s,t] : q)
    {
        l.erase(s); l.erase(t);
        r.insert(s); r.insert(t);
        o = l.ouT()+r.ouT();
        out = min(out,o+sv);
    }
    cout << out << '\n';
}

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