Submission #1014423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014423		orcslop	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	75 ms	8704 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mkp make_pair
#define pii pair<int, int>
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = 1e5 + 5; 

int n, k, add, a, b; 
vector<pii> v; 
ordered_set<pii> st; 
int pref[MAXN], suff[MAXN]; 
priority_queue<int, vector<int>> l; 
priority_queue<int, vector<int>, greater<int>> r; 

void insert(int x){
    int med = (l.empty() ? 1e18 : l.top()); 
    if(x <= med){
        l.push(x); 
        a += x; 
    }
    else{
        r.push(x); 
        b += x; 
    }
    if(r.size() + 1 < l.size()){
        x = l.top(); 
        l.pop(); 
        r.push(x); 
        a -= x; 
        b += x; 
    }
    else if(l.size() < r.size()){
        x = r.top(); 
        l.push(x); 
        r.pop(); 
        a += x; 
        b -= x; 
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> k >> n; 
    if(k == 1){
        vector<int> temp; 
        for(int i = 0; i < n; i++){
            char a, b; 
            int x, y; 
            cin >> a >> x >> b >> y; 
            if(a == b) add += abs(x - y); 
            else{
                temp.pb(x); 
                temp.pb(y); 
            }
        }
        n = sz(temp) / 2; 
        sort(all(temp)); 
        int ans = 0; 
        for(int i = 0; i < 2 * n; i++){
            ans += abs(temp[i] - temp[n]); 
        }
        cout << ans + add + n << '\n'; 
        return 0; 
    }
    for(int i = 0; i < n; i++){
        char a, b; 
        int x, y; 
        cin >> a >> x >> b >> y; 
        if(a == b) add += abs(x - y); 
        else v.pb(mkp(x, y)); 
    }
    n = sz(v); 
    if(n == 0){
        cout << add << '\n'; 
        return 0; 
    }
    sort(all(v), [](pii &p1, pii &p2){
        return (p1.f + p1.s) < (p2.f + p2.s); 
    }); 
    a = 0, b = 0; 
    for(int i = 0; i < n; i++){
        insert(v[i].f); 
        insert(v[i].s); 
        pref[i] = b - a; 
    }
    while(!l.empty()) l.pop(); 
    while(!r.empty()) r.pop(); 
    a = 0, b = 0; 
    for(int i = n - 1; i >= 0; i--){ 
        insert(v[i].f); 
        insert(v[i].s); 
        suff[i] = b - a; 
    }
    int ans = pref[n - 1]; 
    for(int i = 0; i < n - 1; i++){
        ans = min(ans, pref[i] + suff[i + 1]); 
    }
    cout << ans + add + n << '\n'; 
    return 0; 
}

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