Submission #521505

#	Time	Username	Problem	Language	Result	Execution time	Memory
521505		Sharky	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	91 ms	18588 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
#define sz(x) x.size()
#define pq priority_queue
int pref[N], suff[N];
int lps[N], lss[N], rps[N], rss[N], lpcnt[N], lscnt[N], rpcnt[N], rscnt[N];
bool cmp(pair<int, int> x, pair<int, int> y) {
    return x.first + x.second < y.first + y.second;
}
void precompute(vector<pair<int, int> > pv) {
    int nn;
    pq<int> below; pq<int, vector<int>, greater<int> > above;
    int ls = 0, rs = 0;
    for (int i = 1; i < pv.size(); i++) {
        int n = pv[i].first;
        if (below.empty()) {
            below.push(n);
            nn = n;
            ls += n;
        } else if (above.empty()) {
            above.push(n); pref[i] = below.top();
            nn = (above.top() + below.top()) / 2;
            if (above.top() < below.top()) {
                int tmp = below.top();
                int tmp2 = above.top();
                below.pop(); below.push(tmp2);
                above.pop(); above.push(tmp);
                rs += n;
                swap(ls, rs);
            } else {
                rs += n;
            }
        } else {
            if (n <= nn) {
                below.push(n);
                ls += n;
            } else {
                above.push(n);
                rs += n;
            }
            if (sz(below) > sz(above) + 1) {
                int tmp = below.top();
                below.pop();
                above.push(tmp);
                ls -= tmp; rs += tmp;
            } else if (sz(below) < sz(above)) {
                int tmp = above.top();
                above.pop();
                below.push(tmp);
                ls += tmp; rs -= tmp;
            }
            nn = below.top();
        }
        n = pv[i].second;
        if (below.empty()) {
            below.push(n);
            nn = n;
            ls += n;
        } else if (above.empty()) {
            above.push(n); pref[i] = below.top();
            nn = (above.top() + below.top()) / 2;
            if (above.top() < below.top()) {
                int tmp = below.top();
                int tmp2 = above.top();
                below.pop(); below.push(tmp2);
                above.pop(); above.push(tmp);
                rs += n;
                swap(ls, rs);
            } else {
                rs += n;
            }
        } else {
            if (n <= nn) {
                below.push(n);
                ls += n;
            } else {
                above.push(n);
                rs += n;
            }
            if (sz(below) > sz(above) + 1) {
                int tmp = below.top();
                below.pop();
                above.push(tmp);
                ls -= tmp; rs += tmp;
            } else if (sz(below) < sz(above)) {
                int tmp = above.top();
                above.pop();
                below.push(tmp);
                ls += tmp; rs -= tmp;
            }
            nn = below.top();
            pref[i] = nn;
        }
        lps[i] = ls; rps[i] = rs;
        lpcnt[i] = below.size(); rpcnt[i] = above.size();
    }
    ls = 0; rs = 0;
    while (below.size()) below.pop();
    while (above.size()) above.pop();
    for (int i = pv.size() - 1; i >= 1; i--) {
        int n = pv[i].first;
        if (below.empty()) {
            below.push(n);
            nn = n;
            ls += n;
        } else if (above.empty()) {
            above.push(n); suff[i] = below.top();
            nn = (above.top() + below.top()) / 2;
            if (above.top() < below.top()) {
                int tmp = below.top();
                int tmp2 = above.top();
                below.pop(); below.push(tmp2);
                above.pop(); above.push(tmp);
                rs += n;
                swap(ls, rs);
            } else {
                rs += n;
            }
        } else {
            if (n <= nn) {
                below.push(n);
                ls += n;
            } else {
                above.push(n);
                rs += n;
            }
            if (sz(below) > sz(above) + 1) {
                int tmp = below.top();
                below.pop();
                above.push(tmp);
                ls -= tmp; rs += tmp;
            } else if (sz(below) < sz(above)) {
                int tmp = above.top();
                above.pop();
                below.push(tmp);
                ls += tmp; rs -= tmp;
            }
            nn = below.top();
        }
        n = pv[i].second;
        if (below.empty()) {
            below.push(n);
            nn = n;
            ls += n;
        } else if (above.empty()) {
            above.push(n); suff[i] = below.top();
            nn = (above.top() + below.top()) / 2;
            if (above.top() < below.top()) {
                int tmp = below.top();
                int tmp2 = above.top();
                below.pop(); below.push(tmp2);
                above.pop(); above.push(tmp);
                rs += n;
                swap(ls, rs);
            } else {
                rs += n;
            }
        } else {
            if (n <= nn) {
                below.push(n);
                ls += n;
            } else {
                above.push(n);
                rs += n;
            }
            if (sz(below) > sz(above) + 1) {
                int tmp = below.top();
                below.pop();
                above.push(tmp);
                ls -= tmp; rs += tmp;
            } else if (sz(below) < sz(above)) {
                int tmp = above.top();
                above.pop();
                below.push(tmp);
                ls += tmp; rs -= tmp;
            }
            nn = below.top();
            suff[i] = nn;
        }
        lss[i] = ls; rss[i] = rs;
        lscnt[i] = below.size(); rscnt[i] = above.size();
    }
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int sameside = 0, k, n, m = 0, ans = 0; cin >> k >> n;
    vector<pair<int, int> > pv; pv.push_back({0, 0});
    vector<int> v(2 * n + 5);
    for (int i = 1; i <= n; i++) {
        char p, q; int s, t; cin >> p >> s >> q >> t;
        if (p == q) sameside += abs(s - t);
        else {
            if (s > t) swap(s, t);
            m++; v[m] = s;
            m++; v[m] = t;
            pv.push_back({s, t});
        }
    }
    sort(pv.begin(), pv.end(), cmp);
    precompute(pv);
    if (k == 1 || m == 2) {
        sort(v.begin() + 1, v.begin() + m + 1);
        int bridge = v[(m + 1) / 2];
        for (int i = 1; i <= m; i += 2) {
            ans += abs(bridge - v[i]) + abs(bridge - v[i + 1]) + 1;
        }
        cout << ans + sameside << "\n";
    } else {
        int mn = 1e18;
        for (int i = 2; i <= (m / 2); i++) {
            ans = (m / 2);
            ans += (lpcnt[i - 1] * pref[i - 1] - lps[i - 1]);
            ans += (rps[i - 1] - pref[i - 1] * rpcnt[i - 1]);
            ans += (lscnt[i] * suff[i] - lss[i]);
            ans += (rss[i] - suff[i] * rscnt[i]);
            mn = min(mn, ans);
        }
        if (m == 0) mn = 0;
        cout << mn + sameside << "\n";
    }
    return 0;
}

/*
2 7
B 1 A 0
A 0 B 0
B 1 B 1
B 1 A 1
B 0 A 1
B 1 A 0
B 0 A 1
*/

Compilation message (stderr)

bridge.cpp: In function 'void precompute(std::vector<std::pair<long long int, long long int> >)':
bridge.cpp:16:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 1; i < pv.size(); i++) {
      |                     ~~^~~~~~~~~~~
bridge.cpp:36:13: warning: 'nn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |             if (n <= nn) {
      |             ^~

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