Submission #1139816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139816		Persia	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	82 ms	11404 KiB

bridge

#include <bits/stdc++.h>
#define bit(i, x) (x >> i & 1)
#define ll long long
#define sz(x) (int)(x).size()
const int N = 2e5 + 5;
const int mod = 998244353;
using namespace std;

int k, n;
pair<int, int> a[N];
int m;
ll l[N], r[N];

ll bonus;

struct Median{
    multiset<int> l, r;
    ll sl = 0, sr = 0;

    void init() {
        l.clear();
        r.clear();
        sl = sr = 0;
    }

    void insert(int x) {
        if(l.empty()) {
            l.insert(x);
            sl += x;
        }
        else {
            int mx_l = *l.rbegin();
            if(x <= mx_l) {
                l.insert(x);
                sl += x;
            }
            else {
                r.insert(x);
                sr += x;
            }
        }

        while(sz(l) - sz(r) > 1) {
            int top = *l.rbegin();
            l.erase(l.find(top));
            r.insert(top);
            sl -= top;
            sr += top;
        }

        while(sz(r) > sz(l)) {
            int top = *r.begin();
            r.erase(r.find(top));
            l.insert(top);
            sr -= top;
            sl += top;
        }
    }

    int med() {
        return *l.rbegin();
    }

    ll val() {
        int mid = *l.rbegin();
        return 1LL * (sz(l) - sz(r)) * mid - (sl - sr);
    }

    void Print() {
        for(auto i : l) cout << i << " ";
        cout << "\n";
        for(auto i : r) cout << i << " ";
        cout << "\n";
    }
} M;

mt19937 rng(time(0));
int rnd(int l, int r) {
    return rng() % (r - l + 1) + l;
}

signed main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> k >> n;
    for(int i = 1; i <= n; i++) {
        char p, q; int s, t;
        cin >> p >> s >> q >> t;
        if(s > t) swap(s, t);
        if(p == q) {
            bonus += abs(t - s);
        }
        else {
            bonus++;
            a[++m] = {s, t};
        }
    }

    if(k == 2) {
        sort(a + 1, a + m + 1, [&](pair<int, int> x, pair<int, int> y) {
            return (x.first + x.second < y.first + y.second);
        });
        for(int i = 1; i <= m; i++) {
            M.insert(a[i].first);
            M.insert(a[i].second);
            l[i] = M.val();
        }

        M.init();

        for(int i = m; i >= 1; i--) {
            M.insert(a[i].first);
            M.insert(a[i].second);
            r[i] = M.val();
        }

        ll res = LLONG_MAX;
        for(int i = 1; i <= m; i++) res = min(res, l[i] + r[i + 1]);
        cout << res + bonus;
    }
    else {
        sort(a + 1, a + m + 1, [&](pair<int, int> x, pair<int, int> y) {
            return (x.first + x.second < y.first + y.second);
        });
        for(int i = 1; i <= m; i++) {
            M.insert(a[i].first);
            M.insert(a[i].second);
            l[i] = M.val();

//            cout << a[i].first << " " << a[i].second << "\n";
        }

//        M.Print();

//        cout << M.med() << "\n";
        cout << l[m] + bonus;
    }
    return 0 ^ 0;
}

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