Submission #474787

#	Time	Username	Problem	Language	Result	Execution time	Memory
474787		MohammadAghil	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	415 ms	12800 KiB

bridge

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second 
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll mod = 1e9 + 7, maxn = 3e5 + 5, inf = 1e9 + 5;

struct Box{
    multiset<int> low, up;
    ll sup, slow;
    Box(){
        sup = slow = 0;
    }
    void upd(){
        if(sz(low) > sz(up) + 1){
            int t = *prev(low.end());
            slow -= t, sup += t;
            up.insert(t);
            low.erase(prev(low.end()));
        }
        if(sz(up) > sz(low)){
            int t = *up.begin();
            slow += t, sup -= t;
            low.insert(t);
            up.erase(up.begin());
        }
    }
    void insert(int x){
        if(sz(up) && x >= *up.begin()){
            up.insert(x);
            sup += x;
        }else{
            low.insert(x);
            slow += x;
        }
        upd();
    }
    void erase(int x){
        if(sz(up) && x >= *up.begin()){
            up.erase(up.find(x));
            sup -= x;
        }else{
            low.erase(low.find(x));
            slow -= x;
        }
        upd();
    }
    ll get(){
        if(!sz(low)) return 0;
        ll md = *prev(low.end());
        return md*(sz(low) - sz(up)) - slow + sup;
    }
};

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    int k , n; cin >> k >> n;
    ll ans = 0;
    vector<pp> v;
    rep(i,0,n){
        char h, w; 
        int s, e; cin >> h >> s >> w >> e;
        if(h == w){
            ans += abs(s - e);
        }else{
            ans++;
            v.pb({s, e});
        }
    } 
    sort(all(v), [&](pp a, pp b){
        return a.ff + a.ss < b.ff + b.ss;
    });
    Box l, r;
    for(pp c: v){
        r.insert(c.ff);
        r.insert(c.ss);
    }
    if(k == 1){
        ans += r.get();
    }else{
        ll k = r.get();
        for(pp c: v){
            l.insert(c.ff);
            l.insert(c.ss);
            r.erase(c.ff);
            r.erase(c.ss);
            k = min(k, l.get() + r.get());
        }
        ans += k;
    }
    cout << ans;
    return 0;
}

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