제출 #1190644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190644		Gray	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	917 ms	112112 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)1e18
ll MOD = (ll)(1e9+7);

struct Fenwick{
    vector<ll> pref, suff;
    vector<ll> cnt_pref, cnt_suff;
    vector<ll> psb;
    ll n, offs;
    Fenwick(vector<ll> &possibles){
        n=possibles.size()+10; offs=1;
        psb=possibles; sort(psb.begin(), psb.end());
        pref.resize(n+1); suff.resize(n+1); cnt_pref.resize(n+1); cnt_suff.resize(n+1);
    }
    ll i_to_i(ll i){
        return lower_bound(psb.begin(), psb.end(), i)-psb.begin();
    }
    void add_pref(ll i, ll x, ll xf){
        i=i_to_i(i); //cout << x/abs(x) << ln;
        i+=offs; for (; i<=n; i+=(-i&i)) {
            pref[i]+=x; cnt_pref[i]+=xf;
        }
    }
    void add_suff(ll i, ll x, ll xf){
        i=i_to_i(i); //cout << x/abs(x) << ln;
        i+=offs; for (; i; i-=(-i&i)) {
            suff[i]+=x;
            cnt_suff[i]+=xf;
        }
    }
    void add(ll i, ll x, ll xf){
        add_pref(i, x, xf); add_suff(i, x, xf);
    }
    ll query_pref(ll i){
        i=i_to_i(i);
        i+=offs; ll sum=0;
        for (; i; i-=(-i&i))
            sum+=pref[i];
        return sum;
    }
    ll query_suff(ll i){
        i=i_to_i(i);
        i+=offs; ll sum=0;
        for (; i<=n; i+=(-i&i))
            sum+=suff[i];
        return sum;
    }
    ll query_pref_cnt(ll i){
        i=i_to_i(i);
        i+=offs; ll sum=0;
        for (; i; i-=(-i&i))
            sum+=cnt_pref[i];
        return sum;
    }
    ll query_suff_cnt(ll i){
        i=i_to_i(i);
        i+=offs; ll sum=0;
        for (; i<=n; i+=(-i&i))
            sum+=cnt_suff[i];
        return sum;
    }
};

struct Median{
    multiset<ll> big, small;
    void balance(){
        while (big.size()>small.size()){
            small.insert(*big.begin());
            big.erase(big.begin());
        }
        while (big.size()<(big.size()+small.size())/2){
            big.insert(*small.rbegin());
            small.erase(small.find(*small.rbegin()));
        }
        while (!big.empty() and !small.empty() and *big.begin()<*small.rbegin()){
            ll rb = *small.rbegin(); small.erase(small.find(*small.rbegin()));
            ll b = *big.begin(); big.erase(big.begin());
            big.insert(rb); small.insert(b);
        }
    }
    void add(ll x){
        big.insert(x);
        balance();
    }
    void remove(ll x){
        if (small.find(x)!=small.end()){
            small.erase(small.find(x));
        }else{
            big.erase(big.find(x));
        }
        balance();
    }
    ll median(){
        return *small.rbegin();
    }
};

void solve(){
    ll k, n; cin >> k >> n;
    vector<pair<ll, ll>> a;
    ll res=0;
    vector<ll> pts, psb;
    for (ll i=0; i<n; i++){
        char za, zb; ll l, r;
        cin >> za >> l >> zb >> r;
        if (za==zb){
            res+=abs(l-r);
        }else{
            pts.push_back(l); pts.push_back(r);
            psb.push_back(l-1); psb.push_back(l+1);
            psb.push_back(r-1); psb.push_back(r+1);
            psb.push_back(l); psb.push_back(r);
            a.push_back({min(l, r), max(l, r)});
        }
    }
    sort(psb.begin(), psb.end()); psb.erase(unique(psb.begin(), psb.end()), psb.end());
    n=a.size();
    if (n==0){
        cout << res << ln;
    } else if (k==1){
        Fenwick fll(psb), frr(psb);
        ll lsum=0, rsum=0;
        for (ll i=0; i<n; i++){
            lsum+=a[i].ff; rsum+=a[i].ss;
            fll.add(a[i].ff, a[i].ff, 1);
            frr.add(a[i].ss, a[i].ss, 1);
        }
        sort(pts.begin(), pts.end());
        ll add=INF;
        for (auto ch:pts){
            ch = pts[pts.size()/2];
            add=min(add, rsum-lsum+2*(frr.query_pref_cnt(ch-1)*ch-frr.query_pref(ch-1))+2*(fll.query_suff(ch+1)-(fll.query_suff_cnt(ch+1)*ch)));
            break;
        }
        if (!n) add=0;
        // cout << add < ln;
        cout << add+res+n << ln;
    }else{
        Fenwick lfll(psb), lfrr(psb);
        Fenwick rfll(psb), rfrr(psb);
        sort(a.begin(), a.end(), [&](auto &op1, auto &op2){
            return op1.ss+op1.ff<op2.ss+op2.ff;
        });
        ll lLsum=0, lRsum=0, rLsum=0, rRsum=0;
        Median left, right;
        for (ll i=0; i<n; i++) {
            rfll.add(a[i].ff, a[i].ff, 1);
            rfrr.add(a[i].ss, a[i].ss, 1);
            right.add(a[i].ss); right.add(a[i].ff);
            rRsum+=a[i].ss; rLsum+=a[i].ff;
        }
        ll add=rRsum-rLsum+2*(rfrr.query_pref_cnt(right.median()-1)*right.median()-rfrr.query_pref(right.median()-1))+2*(rfll.query_suff(right.median()+1)-(rfll.query_suff_cnt(right.median()+1)*right.median()));
        for (ll i=0; i<n; i++){
            rfll.add(a[i].ff, -a[i].ff, -1); rfrr.add(a[i].ss, -a[i].ss, -1);
            lfll.add(a[i].ff, a[i].ff, 1); lfrr.add(a[i].ss, a[i].ss, 1);
            rRsum-=a[i].ss; rLsum-=a[i].ff; lRsum+=a[i].ss; lLsum+=a[i].ff;
            right.remove(a[i].ff); right.remove(a[i].ss); left.add(a[i].ff); left.add(a[i].ss);

            if (i<n-1){
                add=min(add, rRsum-rLsum+2*(rfrr.query_pref_cnt(right.median()-1)*right.median()-rfrr.query_pref(right.median()-1))+2*(rfll.query_suff(right.median()+1)-(rfll.query_suff_cnt(right.median()+1)*right.median()))+
                lRsum-lLsum+2*(lfrr.query_pref_cnt(left.median()-1)*left.median()-lfrr.query_pref(left.median()-1))+2*(lfll.query_suff(left.median()+1)-(lfll.query_suff_cnt(left.median()+1)*left.median())));
            }
        }
        add=min(add, lRsum-lLsum+2*(lfrr.query_pref_cnt(left.median()-1)*left.median()-lfrr.query_pref(left.median()-1))+2*(lfll.query_suff(left.median()+1)-(lfll.query_suff_cnt(left.median()+1)*left.median())));
        cout << add+res+n << ln;
    }

}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll testc=1;
    // cin >> testc;
    for (ll __c=1; __c<=testc; __c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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