제출 #759040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
759040		udhavvarma03	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	307 ms	13600 KiB

bridge

// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define NUM1 1000000007LL
#define all(a) a.begin(), a.end()
#define beg(a) a.begin(), a.begin()
#define sq(a) ((a)*(a))
#define NUM2 998244353LL
#define MOD NUM2
#define LMOD 1000000006LL
#define fi first
#define se second
typedef long double ld;
const ll MAX = 3000100;
const ll INF = 1e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
class MedianFind{
private:
    multiset<ll> low, hi;
    ll lowsum = 0, hisum = 0;
    ll cnt = 0;
public:
    void balance(){
        while(low.size() < hi.size()){
            ll v = *hi.begin();
            hi.erase(hi.begin());
            hisum -= v;
            low.insert(v);
            lowsum += v;
        }
        while(low.size() > hi.size() + 1){
            ll v = *low.rbegin();
            low.erase(low.find(v));
            lowsum -= v;
            hi.insert(v);
            hisum += v;
        }
    }
    void insert(ll val){
        cnt++;
        if(low.empty()){
            low.insert(val);
            lowsum += val;
            return;
        }
        else{
            if(val > *low.rbegin()){
                hi.insert(val);
                hisum += val;
            }
            else{
                low.insert(val);
                lowsum += val;
            }
            balance();
            return;
        }
    }
    void remove(ll val){
        --cnt;
        if(low.find(val) != low.end()){
            low.erase(low.find(val));
            lowsum -= val;
        }
        else{
            hi.erase(hi.find(val));
            hisum -= val;
        }
        balance();
    }
    ll findMedian(){
        if(low.empty()) return -1;
        return *low.rbegin();
    }
    ll findval(){
        if(cnt == 0) return 0ll;
        ll med = findMedian();
        return (low.size()*med - lowsum + hisum - (med*hi.size()));
    }
};
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll k, n;
    cin >> k >> n;
    ll inval = 0;
    vector<pair<ll, ll>> ed;
    for(ll i = 0; i < n; i++){
        ll s, t;
        char p, q;
        cin >> p >> s >> q >> t;
        if(p == q) inval += abs(s - t);
        else{
            ed.push_back({s, t});
        }
    }
    if(k == 1){
        vector<ll> v;
        for(auto& x: ed){
            v.push_back(x.fi);
            v.push_back(x.se);
        }
        sort(all(v));
        // for(auto& x: v) cerr << x << ' ';
        // cerr << '\n';
        ll k = v.size();
        ll med = v[k/2];
        for(auto& x: v) inval += abs(med - x);
        inval += ed.size();
        cout << inval << '\n';
        exit(0);
    }
    auto cmp = [](pair<ll, ll> a, pair<ll, ll> b){
        return a.fi + a.se < b.fi + b.se;
    };
    sort(all(ed), cmp);
    MedianFind med1, med2;
    n = ed.size();
    for(ll i = 0; i < n; i++){
        med2.insert(ed[i].fi);
        med2.insert(ed[i].se);
    }
    ll minval = med2.findval();
    for(ll i = 0; i < n; i++){
        med1.insert(ed[i].fi);
        med1.insert(ed[i].se);
        med2.remove(ed[i].fi);
        med2.remove(ed[i].se);
        minval = min(minval, med1.findval() + med2.findval());
    }
    cout << minval + inval + ed.size();
    return 0;
}

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