Submission #884501

#	Time	Username	Problem	Language	Result	Execution time	Memory
884501		AnhPham	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	36 ms	7120 KiB

bridge

#include <bits/stdc++.h>

#ifdef OP_DEBUG
    #include <algo/debug.h>
#else
    #define debug(...) 26
#endif

using namespace std;

#define int 	long long // maybe tle?
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()
#define TcT     template <class T

const   int     MOD = (int)1e9 + 7, INF = (int)2e9 + 9, INF64 = (int)4e18 + 18;

TcT>            bool minimize(T &val, const T &upd) { return upd < val ? val = upd, 1 : 0; }
TcT>            bool maximize(T &val, const T &upd) { return upd > val ? val = upd, 1 : 0; }

TcT, class S>   istream &operator >> (istream &scanf, pair <T, S> &u) { return scanf >> u.first >> u.second;        }
TcT, class S>   ostream &operator << (ostream &print, pair <T, S> &u) { return print << u.first << ' ' << u.second; }

void solve();

int32_t main() {
    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(0);
    int testcases = 1;

#define TC 0
    if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */

int k, n;
int same_side;
vector <pair <int, int>> opposite;

struct Median {
    int sum = 0;
    priority_queue <int> left;
    priority_queue <int, vector <int>, greater <int>> right;

    void insert(int x) {
        if (left.empty() || x <= left.top()) {
            sum -= x;
            left.push(x);
            if (sz(left) > sz(right) + 1) {
                x = left.top(); left.pop();

                right.push(x);
                sum += 2 * x;
            }
        } else {
            sum += x;
            right.push(x);
            if (sz(right) > sz(left)) {
                x = right.top(); right.pop();

                left.push(x);
                sum -= 2 * x;
            }
        }
    }
};

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

    for (int i = 1; i <= n; ++i) {
        char p, q; int s, t; cin >> p >> s >> q >> t;

        if (s > t)
            swap(s, t);

        if (p == q)
            same_side += t - s;
        else
            opposite.emplace_back(s, t), ++same_side;
    }

    if (opposite.empty())
        return void(cout << same_side << '\n');

    sort(all(opposite), [&](pair <int, int> a, pair <int, int> b) -> bool {
        return a.first + a.second < b.first + b.second;
    });

    n = sz(opposite);

    vector <int> pref(n + 1);
    Median Med;
    for (int i = 0; i < n; ++i) {
        Med.insert(opposite[i].first);
        Med.insert(opposite[i].second);

        pref[i + 1] = Med.sum;
    }

    int ans = pref[n];

    if (k == 2) {
        Med = Median();
        for (int i = n; i >= 1; --i) {
            Med.insert(opposite[i].first);
            Med.insert(opposite[i].second);

            minimize(ans, pref[i] + Med.sum);
        }
    }

    cout << ans + same_side << '\n';
}

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