Submission #1134862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134862		g4yuhg	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	71 ms	10940 KiB

bridge

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 500005
using namespace std;
ll k, n;
ll ans_goc = 0;
pii a[N];
vector<ll> nenSo;
void sub1() {
    ll ans = inf;
    sort(a + 1, a + 1 + n);
    ll sum = 0;
    ll cur_p = -1;
    ll cnt_r = n, cnt_l = 0;
    for (int i = 1; i <= n; i ++) {
        ll l = a[i].fi, r = a[i].se;
        //cout << i << " " << l << " " << r << " " << sum << endl;
        sum += (r - l) + min(abs(r - cur_p), abs(l - cur_p)) * 2 + 1;
    }
    //cout << "sum bd: " << sum << endl;
    ans = min(ans, sum);
    ll id = 1;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 1; i < nenSo.size(); i ++) {
        ll nxt_p = nenSo[i];
        while (pq.size() && pq.top().fi < nxt_p) {
            cnt_l ++ ;
            pq.pop();
        }
        sum -= cnt_r * (nxt_p - cur_p) * 2;
        sum += cnt_l * (nxt_p - cur_p) * 2;
        while (id <= n && a[id].fi <= nxt_p) {
            cnt_r -- ;
            pq.push({a[id].se, id});
            id ++ ;
        }
        //cout << i << " " << nxt_p << " " << sum << endl; 
        ans = min(ans, sum);
        cur_p = nxt_p;
    }
    cout << ans + ans_goc;
}
ll pf[2001][1001], sf[2001][1001], b[N];
bool cmp(pii a, pii b) {
    return a.fi + a.se < b.fi + b.se;
}
void sub2() {
    if (n == 0) {
        cout << ans_goc;
        return;
    }
    if (n == 1) {
        cout << a[1].se - a[1].fi + 1;
        return;
    }
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i ++) {
        b[i] = a[i].fi + a[i].se;
    }
    for (int i = 1; i < nenSo.size(); i ++) {
        ll sum = 0;
        ll cur_p = nenSo[i];
        for (int j = 1; j <= n; j ++){
            ll l = a[j].fi, r = a[j].se;
            if (l <= cur_p && cur_p <= r) {
                sum += (r - l) + 1;
                pf[i][j] = sum;
                continue;
            }
            sum += (r - l) + min(abs(r - cur_p), abs(l - cur_p)) * 2 + 1;
            pf[i][j] = sum;
        }
        sum = 0;
        for (int j = n; j >= 1; j --){
            ll l = a[j].fi, r = a[j].se;
            if (l <= cur_p && cur_p <= r) {
                sum += (r - l) + 1;
                sf[i][j] = sum;
                continue;
            }
            sum += (r - l) + min(abs(r - cur_p), abs(l - cur_p)) * 2 + 1;
            sf[i][j] = sum;
        }
    }
    ll ans = inf;
    for (int i = 1; i < nenSo.size(); i ++) {
        for (int j = i + 1; j < nenSo.size(); j ++) {
            ll l = nenSo[i], r = nenSo[j];
            auto it = upper_bound(b + 1, b + 1 + n, l + r) - b - 1;
            ans = min(ans, pf[i][it] + sf[j][it + 1]);
        }
    }
    cout << ans + ans_goc;
}
ll prefix[N], suffix[N], pre_me[N], suf_me[N], sum_mx, sum_mn;
priority_queue<ll, vector<ll>, greater<ll>> min_heap;
priority_queue<ll> max_heap;
void add(ll num) {
    if (max_heap.size() == 0 || num <= max_heap.top()) {
        max_heap.push(num);
        sum_mx += num;
    }
    else {
        min_heap.push(num);
        sum_mn += num;
    }
    if (max_heap.size() > min_heap.size() + 1) {
        min_heap.push(max_heap.top());
        sum_mn += max_heap.top();
        sum_mx -= max_heap.top();
        max_heap.pop();
    }
    else if (min_heap.size() > max_heap.size()) {
        max_heap.push(min_heap.top());
        sum_mx += min_heap.top();
        sum_mn -= min_heap.top();
        min_heap.pop();
    }
}
ll find_med() {
    if (max_heap.size() >= min_heap.size()) {
        return max_heap.top();
    }
    if (min_heap.size() > max_heap.size()) {
        return min_heap.top();
    }
    return max_heap.top();
}
void sub3() {
    if (n == 0) {
        cout << ans_goc;
        return;
    }
    if (n == 1) {
        cout << a[1].se - a[1].fi + 1;
        return;
    }
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i ++) {
        b[i] = a[i].fi + a[i].se;
    }
    for (int i = 1; i <= n; i ++) {
        ll ps = a[i].fi, pe = a[i].se;
        add(ps);
        add(pe);
        pre_me[i] = find_med();
        ll med = pre_me[i];
        prefix[i] = med * max_heap.size() - sum_mx + sum_mn - med * min_heap.size();
    }
    while (max_heap.size()) max_heap.pop();
    while (min_heap.size()) min_heap.pop();
    sum_mn = sum_mx = 0;
    ll ans = inf;
    for (int i = n; i >= 1; i --) {
        ll ps = a[i].fi, pe = a[i].se;
        add(ps);
        add(pe);
        suf_me[i] = find_med();
        ll med = suf_me[i];
        suffix[i] = med * max_heap.size() - sum_mx + sum_mn - med * min_heap.size();
    }
    for (int i = 1; i <= n - 1; i ++) {
        ans = min(ans, prefix[i] + suffix[i + 1]);
    }
    cout << ans + ans_goc + n;
}
signed main(void) {
    faster;
    ll curid = 0;
    cin >> k >> n;
    for (int i = 1; i <= n; i ++) {
        char bs1, bs2; ll p1, p2;
        cin >> bs1 >> p1 >> bs2 >> p2;
        if (bs1 == bs2) {
            ans_goc += abs(p1 - p2);
            continue;
        }
        curid ++ ;
        if (p1 > p2) swap(p1, p2);
        a[curid] = {p1, p2};
        nenSo.push_back(p1);
        nenSo.push_back(p2);
    }
    n = curid;
    nenSo.push_back(-inf);
    sort(nenSo.begin(), nenSo.end());
    nenSo.resize(unique(nenSo.begin(), nenSo.end()) - nenSo.begin());
    if (k == 1) {
        sub1();
    }
    else if (k == 2) {
        sub3();
    }
    return 0;
}

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