Submission #1294224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294224		nathako9n	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	36 ms	7876 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;
ll que(int i){ ll sm=0; for(; i>=1; i-=i&-i) sm += tr[i]; return sm; }
void up(int i,ll x){ for(; i<=maxn; i+=i&-i) tr[i] += x; }
map<ll,ll> pos;
ll ans = 0;
ll cal(){
    if(st.size() < 2) return 0;
    int idx = (int)(st.size()/2);
    idx--;
    auto xx = st.find_by_order((size_t)idx);
    ll x = xx->first;
    ll low = 0, hi = 0;
    if(pos[x]-1 > 0) low = que(pos[x]-1);
    hi = que(maxn) - que(pos[x]);
    return (x*idx - low) + (hi - x*(idx+1));
}
vector<tuple<ll,ll,ll>> vec;
vector<ll> pf, suf;

int main(){
    king;
    cin >> k >> n;
    maxn = 2 * n;
    tr.assign(maxn + 3, 0);
    vector<ll> com;
    vector<ll> k1;

    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;
            return 0;
        }
        sort(all(k1));
        size_t m = k1.size();
        size_t mid = m/2;
        if(mid == 0){
            cout << ans;
            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));
        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);

    sort(vec.begin(), vec.end(), [](const tuple<ll,ll,ll> &A, const tuple<ll,ll,ll> &B){
        ll ax = min(get<1>(A), get<2>(A));
        ll bx = min(get<1>(B), get<2>(B));
        return ax < bx;
    });
    pf.assign(vec.size(), 0);
    suf.assign(vec.size(), 0);

    ll 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++});
        up((int)pos[x], x); up((int)pos[y], y);
        pf[i] = cal();
    }

    st.clear();
    reverse(all(vec));
    fill(tr.begin(), tr.end(), 0);
    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++});
        up((int)pos[x], x); up((int)pos[y], y);
        suf[(vec.size()-1) - i] = cal();
    }

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

    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;
    return 0;
}

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