Submission #552264

#	Time	Username	Problem	Language	Result	Execution time	Memory
552264		Blossomstream	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	391 ms	14396 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k;
vector<pair<int, int> > v;
int a[100000];
int b[100000];
int main() {
    cin >> k >> n;
    int c = 0;
    ll s = 0;
    for(int i = 0; i < n; i++) {
        int h, t;
        char p, q;
        cin >> p >> h >> q >> t;
        if(p != q) {
            v.push_back(make_pair(h + t, c));
            a[c] = min(h, t);
            b[c] = max(h, t);
            c++;
        } else {
            s += (ll) abs(h - t);
        }
    }
    if(c == 0) {
        cout << s << endl;
        return 0;
    }
    s += (ll) v.size();
    sort(v.begin(), v.end());
    vector<int> w;
    multiset<int> m1;
    multiset<int> m2;
    for(int i = 0; i < c; i++) {
        w.push_back(a[i]);
        w.push_back(b[i]);
        m2.insert(a[i]);
        m2.insert(b[i]);
    }
    sort(w.begin(), w.end());
    int y = w[c - 1];
    int x = -1;
    int r1 = 0, r = 0, l = 0;
    for(int i = 0; i < 2*c; i++) {
        s += (ll) abs(w[i] - y);
        if(w[i] == y) {
            if(i > c - 1) r1++;
            else if(i < c - 1) l++;
        }
    }
    if(k == 1) {
        cout << s << endl;
        return 0;
    }
    ll ans = s;
    for(int j = 0; j < c - 1; j++) {
        int i = v[j].second;
        m1.insert(a[i]);
        m1.insert(b[i]);
        m2.erase(m2.find(a[i]));
        m2.erase(m2.find(b[i]));
        if(a[i] > b[i]) swap(a[i], b[i]);
        if(a[i] > x ) {
            if(r > 0) {
                r--;
            } else {
                x = *m1.upper_bound(x);
                r = m1.count(x) - 1;
            }
            s += ((ll) a[i] + b[i] - 2*x);
        } else if(b[i] >= x && a[i] <= x) {
            if(b[i] == x) r++;
            s += ((ll) b[i] - a[i]);
        } else if(a[i] == x) {
            s += ((ll) b[i] - x);
        }
        if(b[i] < y) {
            if(r1 > 0) {
                r1--;
                l++;
            } else {
                y = *m2.upper_bound(y);
                r1 = m2.count(y) - 1;
                l = 0;
            }
            s -= ((ll) 2*y - a[i] - b[i]);
        } else if(b[i] > y && a[i] <= y) {
            s -= ((ll) b[i] - a[i]);
            if(a[i] == y) {
                if(l > 0) l--;
                else {
                    y = *prev(m2.lower_bound(y));
                    r1 = 0;
                    l = m2.count(y) - 1;
                }
            }
        } else if(b[i] == y) {
            if(r1 > 0) {
                r1--;
                if(a[i] == y) {
                    if(l > 0) l--;
                    else {
                        y = *prev(m2.lower_bound(y));
                        r1 = 0;
                        l = m2.count(y) - 1;
                    }
                }
            } else {
                y = *m2.upper_bound(y);
                r1 = m2.count(y) - 1;
                l = 0;
            }
            s -= ((ll) 2*y - a[i] - b[i]);
        }
        ans = min(ans, s);
    }
    cout << ans << endl;
}

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