Submission #229983

#	Time	Username	Problem	Language	Result	Execution time	Memory
229983		lyc	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	139 ms	13048 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii = pair<int,int>;

const int MX_N = 1e5+5;

int K, N;
char P[MX_N], Q[MX_N];
int S[MX_N], T[MX_N];

struct Mean {
    multiset<int> st;
    multiset<int>::iterator mid;
    long long c;

    Mean(): mid(st.end()), c(0) {}

    void add(int x) {
        auto it = st.lower_bound(x);
        if (mid == st.end()) {
            st.insert(it,x);
            mid = st.begin();
        } else {
            int s = SZ(st);
            st.insert(it,x);
            if (s&1) {
                if (x <= *mid) {
                    c -= x;
                    c += *mid;
                    --mid;
                } else {
                    c += x;
                    c -= *mid;
                }
            } else {
                if (x <= *mid) {
                    c -= x;
                    c += *mid;
                } else {
                    c += x;
                    c -= *next(mid);
                    ++mid;
                }
            }
        }
    };

    void del(int x) {
        auto it = st.lower_bound(x);
        int s = SZ(st);
        if (it == mid) {
            if (s == 1) mid = st.end();
            else if (s&1) --mid;
            else {
                c += *mid;
                c -= *next(mid);
                ++mid;
            }
            st.erase(it);
        } else {
            st.erase(it);
            if (s&1) {
                if (x <= *mid) {
                    c += x;
                    c -= *mid;
                } else {
                    c -= x;
                    c += *mid;
                    --mid;
                }
            } else {
                if (x <= *mid) {
                    c += x;
                    c -= *next(mid);
                    ++mid;
                } else {
                    c -= x;
                    c += *mid;
                }
            }
        }
    }

    long long get() {
        return c;
    }

    void dbg() {
        cout << "mid: ";
        if (mid == st.end()) cout << "NULL";
        else cout << *mid << " (" << distance(st.begin(),mid) << ")";
        cout << endl;

        cout << "st: ";
        for (auto& x : st) cout << x << ' ';
        cout << endl;

        cout << "c: " << c;
        cout << endl;

        cout << endl;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> K >> N;
    long long ans = 0;
    FOR(i,1,N){
        cin >> P[i] >> S[i] >> Q[i] >> T[i];
        if (P[i] == Q[i]) ans += abs(S[i]-T[i]);
        else ans += 1;
    }

    //Mean m;

    //FOR(i,1,10) m.add(i);
    //m.dbg();
    //m.del(5);
    //m.dbg();
    //m.del(6);
    //m.dbg();
    //m.del(1);
    //m.dbg();
    //m.del(10);
    //m.dbg();

    //return 0;

    if (K == 1) {
        Mean m;
        FOR(i,1,N) if (P[i] != Q[i]) { 
            m.add(S[i]);
            m.add(T[i]);
            //m.dbg();
        }
        ans += m.get();
        cout << ans << '\n';
    } else {
        vector<ii> inv;
        FOR(i,1,N) if (P[i] != Q[i]) {
            inv.emplace_back(S[i],T[i]);
        }
        sort(ALL(inv),[](ii a, ii b){
                if (a.first+a.second == b.first+b.second) {
                if (a.first == b.first) return a.second < b.second;
                return a.first < b.first;
                }
                return (a.first+a.second < b.first+b.second);
                });

        long long mini = 1e18;
        Mean l, r;
        for (auto& x : inv) {
            r.add(x.first);
            r.add(x.second);
        }

        FOR(i,0,SZ(inv)-1){
            auto x = inv[i];
            //TRACE(i _ x.first _ x.second);
            //cout << "L" << endl;
            l.add(x.first); l.add(x.second);
            //cout << "R" << endl;
            r.del(x.first); r.del(x.second);
            long long cur = l.get() + r.get();
            mini = min(mini,cur);
        }
        ans += mini;
        cout << ans << '\n';
    }
}

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