Submission #1132163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132163		biank	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	151 ms	12172 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)

#define sz(c) int((c).size())
#define all(c) begin(c), end(c)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define fst first
#define snd second

const ll INF=1e18;

struct Median{
    multiset<int> l,r;
    ll lsum,rsum;
    Median(){
        l.clear(),r.clear();
        lsum=0,rsum=0;
    }
    void balance(){
        if(sz(l)>sz(r)+1){
            rsum+=*l.rbegin(); lsum-=*l.rbegin();
            r.insert(*l.rbegin());

            l.erase(prev(end(l)));
        }
        if(sz(r)>sz(l)){
            rsum-=*begin(r); lsum+=*begin(r);
            l.insert(*begin(r));
            r.erase(begin(r));
        }
    }
    int getMedian(){
        return *l.rbegin();
    }
    void add(int x){
        if(l.empty()||x<getMedian()){
            lsum+=x,l.insert(x);
        }else{
            rsum+=x,r.insert(x);
        }
        balance();
    }
    void erase(int x){
        auto it=r.find(x);
        if(it!=end(r)){
            rsum-=x,r.erase(it);
        }else{
            lsum-=x,l.erase(l.find(x));
        }
        balance();
    }
    ll getCost(){
        return rsum-lsum+(sz(r)-sz(l))*getMedian();
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int k,n;
    cin>>k>>n;
    vector<ii> pos;
    ll res=0;
    forn(i,n){
        char p,q;
        int s,t;
        cin>>p>>s>>q>>t;
        if(p==q) res+=abs(s-t);
        else pos.emplace_back(s,t); 
    }
    int m=sz(pos);
    res+=m;
    sort(all(pos),[&](const ii &lhs, const ii &rhs){
        return lhs.fst+lhs.snd<rhs.fst+rhs.snd;
    });
    vector<ll> pref(m+1,0);
    Median ds;
    forn(i,m){
        ds.add(pos[i].fst),ds.add(pos[i].snd);
        pref[i+1]=ds.getCost();
    }
    if(k==1){
        res+=pref[m];
    }else{
        ds=Median();
        vector<ll> suff(m+1,0);
        dforn(i,m){
            ds.add(pos[i].fst),ds.add(pos[i].snd);
            suff[i]=ds.getCost();
        }
        ll mini=INF;
        forn(i,m+1) mini=min(mini,pref[i]+suff[i]);
        res+=mini;
    }
    cout<<res<<'\n';
    
    return 0;
}

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