Submission #1307690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307690		biank	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	231 ms	10600 KiB

bridge

#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define sum(x) accumulate(all(x), 0LL)

#define pb push_back
#define eb emplace_back

#define fst first
#define snd second

struct ds {
    struct : multiset<int> {
        ll sum = 0;
        void ins(int x) {
            sum += x;
            insert(x);
        }
        void del(int x) {
            sum -= x;
            erase(find(x));
        }
    } left,  right;
    void balance() {
        while (sz(left) > sz(right)) {
            int x = *left.rbegin();
            left.del(x);
            right.ins(x);
        }
        while (sz(right) > sz(left) + 1) {
            int x = *right.begin();
            right.del(x);
            left.ins(x);
        }
    }
    void insert(int x) {
        if (!right.empty() && x < *right.begin()) left.ins(x);
        else right.ins(x);
        balance();
    }
    void erase(int x) {
        if (left.count(x)) left.del(x);
        else right.del(x);
        balance();
    }
    ll query() {
        return - left.sum + right.sum + *right.begin() * (sz(left) - sz(right));
    }
};

const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int k, n;
    cin >> k >> n;
    vii v;
    ll base = 0;
    forn(i, n) {
        char type[2]; int pos[2];
        forn(j, 2) cin >> type[j] >> pos[j];
        if (type[0] == type[1]) base += abs(pos[0] - pos[1]);
        else v.eb(pos[0], pos[1]), base++;
    }
    n = sz(v);
    
    sort(all(v), [&](ii a, ii b) {
        return a.fst + a.snd < b.fst + b.snd;
    });
    
    ds pref, suff;
    forn(i, n) suff.insert(v[i].fst), suff.insert(v[i].snd);
    ll ret = suff.query();
    if (k == 1) {
        ret += base;
        cout << ret << '\n';
        return 0;
    }
    forn(i, n - 1) {
        pref.insert(v[i].fst), pref.insert(v[i].snd);
        suff.erase(v[i].fst), suff.erase(v[i].snd);
        ret = min(ret, pref.query() + suff.query());
    }
    ret += base;
    cout << ret << '\n';
    
    return 0;
}

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