Submission #624960

#	Time	Username	Problem	Language	Result	Execution time	Memory
624960		KoD	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	109 ms	8724 KiB

bridge

#include <bits/stdc++.h>

using ll = long long;
using std::vector;

template <class T>
constexpr T inf = std::numeric_limits<T>::max() / 2;

class slope_trick {
    std::priority_queue<int> left;
    std::priority_queue<int, vector<int>, std::greater<>> right;
    ll min;

  public:
    slope_trick() : left(), right(), min(0) {}

    void add(const int x) {
        if (!left.empty() and x < left.top()) {
            min += left.top() - x;
            left.push(x);
            right.push(left.top());
            left.pop();
        } else {
            right.push(x);
        }
        if (!right.empty() and x > right.top()) {
            min += x - right.top();
            right.push(x);
            left.push(right.top());
            right.pop();
        } else {
            left.push(x);
        }
    }

    ll minimum() const {
        return min;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int K, N;
    std::cin >> K >> N;
    vector<int> S, T;
    ll must = 0;
    while (N--) {
        char p, q;
        int a, b;
        std::cin >> p >> a >> q >> b;
        if (p == q) {
            must += std::abs(a - b);
        } else {
            must += 1;
            S.push_back(a);
            T.push_back(b);
        }
    }
    N = (int)S.size();
    vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](const int i, const int j) {
        return S[i] + T[i] < S[j] + T[j];
    });
    vector<ll> pref(N + 1), suff(N + 1);
    slope_trick slope; 
    for (int i = 0; i < N; ++i) {
        const int k = ord[i];
        slope.add(S[k]);
        slope.add(T[k]);
        pref[i + 1] = slope.minimum();
    }
    slope = slope_trick();
    for (int i = N - 1; i >= 0; --i) {
        const int k = ord[i];
        slope.add(S[k]);
        slope.add(T[k]);
        suff[i] = slope.minimum();
    }
    if (K == 1) {
        std::cout << must + pref[N] << '\n';
    } else {
        ll min = inf<ll>;
        for (int i = 0; i <= N; ++i) {
            min = std::min(min, pref[i] + suff[i]);
        }
        std::cout << must + min << '\n';
    }
}

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