Submission #1014407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014407		orcslop	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	32 ms	3536 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; 
vector<pii> v; 
ordered_set<pii> st; 
int pref[MAXN], suff[MAXN]; 

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; 
    }
    int a = 0, b = 0, med = 0; 
    sort(all(v), [](pii &p1, pii &p2){
        return (p1.f + p1.s) < (p2.f + p2.s); 
    }); 
    for(int i = 0; i < n; i++){
        st.insert(mkp(v[i].f, 2 * i)); 
        st.insert(mkp(v[i].s, 2 * i + 1)); 
        if(v[i].f > med && v[i].s > med){
            med = (*st.find_by_order(i)).f; 
            a += med; 
            b += v[i].f + v[i].s - med; 
        } 
        else{
            a += v[i].f; 
            b += v[i].s; 
        }
        pref[i] = b - a; 
    }
    while(!st.empty()) st.erase(st.begin()); 
    a = 0, b = 0, med = 1e18; 
    for(int i = n - 1; i >= 0; i--){
        st.insert(mkp(v[i].f, 2 * i)); 
        st.insert(mkp(v[i].s, 2 * i + 1)); 
        if(v[i].f < med && v[i].s < med){
            med = (*st.find_by_order(n - i)).f; 
            a += v[i].f + v[i].s - med; 
            b += med;
        }
        else{
            a += v[i].f; 
            b += v[i].s; 
        }
        suff[i] = b - a; 
    }
    int ans = 1e18; 
    for(int i = 0; i < n - 1; i++){
        ans = min(ans, pref[i] + suff[i + 1]); 
    }
    cout << add + ans + n << '\n'; 
    return 0; 
}

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