Submission #1294202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294202		nathako9n	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	2 ms	336 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 pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define eb emplace_back
#define mpr make_pair
#define fi first
#define sec second
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define king ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(0)
#define fore(i,a,b) for(int i=(a); i<=(b); ++i)
#define forr(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,n) for(int i=1;i<=(n);++i)
#define rep2(i,n) for(int i=0;i<(n);++i)

const int N = 1e5+3;
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(){
    int idx = st.size()/2;
    idx--;
    auto xx = st.find_by_order(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;
ll pf[N+2],suf[N+2];



int main(){
    king;
    cin>>k>>n;
    vector<ll>k1;
    maxn = 2*n;
    tr.assign(maxn+3, 0);
    vector<ll> com;
    fore(i,1,n){
        char q,w;
        int x,y;

        cin>>q>>x>>w>>y;
        if(q==w){
            ans += abs(x-y);
        }
        else{ans++;vec.pb({(x+y)/2,x,y});if(k==1){k1.pb(x);k1.pb(y);}}
        com.pb(x);com.pb(y);

    }
    if(k==1){
        map<ll,ll> freq;
        sort(all(k1));
        ll low = 0,hi=0, mid = (k1.size()/2)-1;
        ll x=k1[mid];

//        for(auto i : k1)cout << i << " ";
//        cout << endl;
        fore(i,0,mid-1){low+=(k1[i]);}
        fore(i,mid+1,k1.size()-1)hi+=(k1[i]);
      cout << ans +(x*mid - low) + (hi - x*(mid+1));
//        cout << mid << " " << x  << " " << (x*mid - low) << " " << (hi - x*(mid+1));
//        cout << endl << low << " " << hi;
        return 0;
    }
    sort(all(com));
    com.erase(unique(all(com)), com.end());
    fore(i,0,com.size()-1){
        pos[com[i]] = i+1;
    }
    sort(all(vec));
    ll cnt = 0;
    fore(i,0,vec.size()-1){
        auto [s,x,y] = vec[i];
        st.insert({x,cnt++}); st.insert({y,cnt++});
        up(pos[x],x); up(pos[y], y);
        pf[i]=cal();
    }
    st.clear();
    ll mn = 1e18;
    reverse(all(vec));

    fill(tr.begin(), tr.end(), 0);
    cnt = 0;
    fore(i,0,vec.size()-1){
        auto [s,x,y] = vec[i];
        st.insert({x,cnt++}); st.insert({y,cnt++});
        up(pos[x],x); up(pos[y], y);
        suf[(vec.size()-1)-i]=cal();
    }
    if(vec.empty()){
        cout<<ans;
        return 0;
    }
    if(vec.size() == 1){
        mn = min(pf[0], suf[0]);
    } else {
        fore(i,0,(int)vec.size()-2){
            mn = min(mn, pf[i] + suf[i+1]);
        }
    }
    cout<<mn+ans;

    return 0;
}

/*

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7


1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

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