Submission #1083784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083784		TrinhKhanhDung	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	155 ms	13328 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int LOG = 18;

struct fen{
    int n;
    vector<ll> tree;

    fen(int _n = 0){
        n = _n;
        tree.resize(n + 3, 0);
    }

    void upd(int p, ll c){
        while(p <= n){
            tree[p] += c;
            p += p & -p;
        }
    }

    ll get(int p){
        ll ans = 0;
        while(p > 0){
            ans += tree[p];
            p -= p & -p;
        }
        return ans;
    }

    ll get(int l, int r){
        return get(r) - get(l - 1);
    }

    int find(int k){
        if(get(n) < k) return n + 1;
        int p = 0, sum = 0;
        for(int i=LOG-1; i>=0; i--){
            if(p + MASK(i) <= n && sum + tree[p + MASK(i)] < k){
                sum += tree[p + MASK(i)];
                p += MASK(i);
            }
        }
        return p + 1;
    }
};

void solve(){
    int n, k;
    cin >> k >> n;

    ll ans = 0, res = 0;
    vector<int> ord, L, R;
    vector<pair<int, int>> a;
    for(int i=0; i<n; i++){
        char t1, t2;
        int p1, p2;
        cin >> t1 >> p1 >> t2 >> p2;
        ans += abs(p1 - p2);
        if(t1 != t2){
            ord.push_back(p1);
            ord.push_back(p2);
            ans++;
            res++;
            L.push_back(min(p1, p2));
            R.push_back(max(p1, p2));
            a.push_back(make_pair(min(p1, p2), max(p1, p2)));
        }
        else{
            res += abs(p1 - p2);
        }
    }
    if(L.empty()){
        cout << ans << '\n';
        return;
    }
    if(k == 1){
        cps(ord);
        sort(ALL(L));
        sort(ALL(R));
        vector<ll> pre(sz(L) + 3, 0), suf(sz(R) + 3, 0);
        for(int i=1; i<=sz(L); i++){
            pre[i] = pre[i - 1] + R[i - 1];
        }
        for(int i=sz(L); i>=1; i--){
            suf[i] = suf[i + 1] + L[i - 1];
        }
        ll ma = oo;
        for(int x: ord){
            int pl = lower_bound(ALL(R), x) - R.begin();
            int pr = lower_bound(ALL(L), x) - L.begin() + 1;
            minimize(ma, 2LL * (1LL * x * pl - pre[pl] + suf[pr] - 1LL * x * (sz(L) - pr + 1)));
        }
        cout << ans + ma << '\n';
    }

    fen bit(5);
    for(int i=1; i<=5; i++){
        bit.upd(i, 1);
    }
//    for(int i=1; i<=5; i++){
//        bit.upd(i, -1);
//        cout << bit.find(1);
//    }

    if(k == 2){
        sort(ALL(ord));
        fen cntL(sz(ord)), sumL(sz(ord)), cntR(sz(ord)), sumR(sz(ord));
        sort(ALL(a), [&](pair<int, int> a, pair<int, int> b){return a.fi + a.se < b.fi + b.se;});
        for(int i=1; i<=sz(ord); i++){
            cntR.upd(i, 1);
            sumR.upd(i, ord[i - 1]);
        }

        //relabel
        fen bit(sz(ord));
        for(int i=1; i<=sz(ord); i++){
            bit.upd(i, 1);
        }
        for(pair<int, int> &o: a){
            int l = lower_bound(ALL(ord), o.fi) - ord.begin();
            int r = lower_bound(ALL(ord), o.se) - ord.begin();
            o.fi = bit.find(bit.get(l) + 1);
            bit.upd(o.fi, -1);
            o.se = bit.find(bit.get(r) + 1);
            bit.upd(o.se, -1);
        }

        ll sum = oo;

        for(pair<int, int> o: a){
            cntR.upd(o.fi, -1); cntR.upd(o.se, -1);
            sumR.upd(o.fi, -ord[o.fi - 1]); sumR.upd(o.se, -ord[o.se - 1]);
            cntL.upd(o.fi, 1); cntL.upd(o.se, 1);
            sumL.upd(o.fi, ord[o.fi - 1]); sumL.upd(o.se, ord[o.se - 1]);

            int nL = cntL.get(sz(ord)), nR = cntR.get(sz(ord));
            int pL = cntL.find((nL + 1) / 2);
            int pR = cntR.find((nR + 1) / 2);
            ll cur = sumL.get(pL + 1, sz(ord)) - sumL.get(1, pL) + sumR.get(pR + 1, sz(ord)) - sumR.get(1, pR);
//            cout << o.fi << ' ' << o.se << ' ' << pL << ' ' << pR << '\n';
            minimize(sum, cur);
        }
        cout << res + sum << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("flowers.inp", "r", stdin);
    // freopen("flowers.out", "w", stdout);

    int nTest = 1;
//    cin >> nTest;
    while(nTest--)
        solve();

    return 0;
}

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