Submission #1294232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294232		nathako9n	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	36 ms	8664 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;
typedef tree<pair<long long,long long>,null_type,less<pair<long long,long long>>,rb_tree_tag,tree_order_statistics_node_update> oset;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define all(x) (x).begin(), (x).end()
#define king ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(0)

int n, k, maxn;
oset st;
vector<ll> tr;      // sums
vector<int> trCnt;  // counts

// Fenwick for sums
ll queSum(int i){
    ll sm=0;
    for(; i>=1; i-=i&-i) sm += tr[i];
    return sm;
}
void upSum(int i,ll x){
    for(; i<=maxn; i+=i&-i) tr[i] += x;
}

// Fenwick for counts
int queCnt(int i){
    int sm=0;
    for(; i>=1; i-=i&-i) sm += trCnt[i];
    return sm;
}
void upCnt(int i,int x){
    for(; i<=maxn; i+=i&-i) trCnt[i] += x;
}

map<ll,int> pos;
ll totalSumAll = 0;

ll cal(bool useLeftMedian){
    if(st.size() == 0) return 0;
    // choose median index (order in st)
    size_t sz = st.size();
    size_t posIndex;
    if(useLeftMedian){
        // left median for even size
        posIndex = sz/2 - 1;
    } else {
        // right median for even size
        posIndex = sz/2;
    }
    // get iterator to that ordered element
    auto it = st.find_by_order(posIndex);
    ll x = it->first;
    // compressed position of value x
    int p = pos[x];

    // counts and sums strictly less than value x
    int countLess = queCnt(p-1);
    ll sumLess = queSum(p-1);

    // total count left of chosen pair in st (including equal-values that are before this pair)
    int countLeft = (int)posIndex;
    // number of equal-value elements that are before the chosen pair
    int equalBefore = countLeft - countLess;
    // low should include sumLess plus equalBefore * x
    ll low = sumLess + (ll)equalBefore * x;

    // counts and sums strictly greater than value x
    int countGreater = queCnt(maxn) - queCnt(p);
    ll sumGreater = queSum(maxn) - queSum(p);
    // number of elements strictly after chosen pair in st
    int countRight = (int)sz - (int)posIndex - 1;
    // sum of elements after chosen pair equals sumGreater (elements equal to x after the chosen pair contribute 0 to distance)
    ll hi = sumGreater;

    ll leftCost = x * (ll)countLeft - low;
    ll rightCost = hi - x * (ll)countRight;
    return leftCost + rightCost;
}

vector<tuple<ll,ll,ll>> vec;
vector<ll> pf, suf;

int main(){
    king;
    cin >> k >> n;
    maxn = 2 * n + 5;
    tr.assign(maxn + 5, 0);
    trCnt.assign(maxn + 5, 0);

    vector<ll> com;
    vector<ll> k1;
    ll ans = 0;

    for(int i = 1; i <= n; ++i){
        char q,w;
        int x,y;
        cin >> q >> x >> w >> y;
        if(q == w){
            ans += llabs((ll)x - (ll)y);
        } else {
            ans++;
            vec.push_back({(x + y) / 2, x, y});
            if(k == 1){
                k1.push_back(x);
                k1.push_back(y);
            }
        }
        com.push_back(x);
        com.push_back(y);
    }

    if(k == 1){
        if(k1.empty()){
            cout << ans << '\n';
            return 0;
        }
        sort(all(k1));
        size_t m = k1.size();
        size_t mid = m/2;
        // choose left median (either left or right median gives same minimal sum for even count)
        if(mid == 0){
            cout << ans << '\n';
            return 0;
        }
        mid = mid - 1;
        ll x = k1[mid];
        ll low = 0, hi = 0;
        for(size_t i = 0; i < mid; ++i) low += k1[i];
        for(size_t i = mid+1; i < m; ++i) hi += k1[i];
        cout << ans + (x * (ll)mid - low) + (hi - x * (ll)(mid + 1)) << '\n';
        return 0;
    }

    sort(all(com));
    com.erase(unique(all(com)), com.end());
    for(size_t i = 0; i < com.size(); ++i) pos[com[i]] = (int)(i + 1);

    if(vec.empty()){
        cout << ans << '\n';
        return 0;
    }

    pf.assign(vec.size(), 0);
    suf.assign(vec.size(), 0);

    // prefix pass (use left median)
    size_t cnt = 0;
    for(size_t i = 0; i < vec.size(); ++i){
        auto [s,x,y] = vec[i];
        st.insert({x, cnt++});
        st.insert({y, cnt++});
        upSum(pos[x], x);
        upSum(pos[y], y);
        upCnt(pos[x], 1);
        upCnt(pos[y], 1);
        pf[i] = cal(true); // left median
    }

    // suffix pass: clear and rebuild from reversed vec (use right median)
    st.clear();
    fill(tr.begin(), tr.end(), 0);
    fill(trCnt.begin(), trCnt.end(), 0);
    cnt = 0;
    reverse(all(vec));
    for(size_t i = 0; i < vec.size(); ++i){
        auto [s,x,y] = vec[i];
        st.insert({x, cnt++});
        st.insert({y, cnt++});
        upSum(pos[x], x);
        upSum(pos[y], y);
        upCnt(pos[x], 1);
        upCnt(pos[y], 1);
        suf[(vec.size()-1) - i] = cal(false); // right median
    }

    ll mn = (ll)4e18;
    if(vec.size() == 1){
        mn = min(pf[0], suf[0]);
    } else {
        for(size_t i = 0; i + 1 < vec.size(); ++i){
            mn = min(mn, pf[i] + suf[i+1]);
        }
    }

    cout << mn + ans << '\n';
    return 0;
}

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