Submission #1288187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288187		gustavo_d	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	2 ms	4932 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5;
const ll INF = 1e10;
const ll INFLL = 1e18;

struct Event {
    int type; ll x; int i; // 0: open 1: close
    Event(int _type=0, ll _x=0, int _i=0):
        type(_type), x(_x), i(_i) {}
};

int k, n;

ll a[MAXN], b[MAXN], all[2*MAXN];
Event events[2*MAXN];
vector<pair<ll, int>> toB1;
int status[MAXN];

ll ans = INFLL, b1 = -INF;

bool cmp(Event a, Event b) {
    if (a.x == b.x) {
        return a.type < b.type;
    }
    return a.x < b.x;
}

void solve(int idxB2) {
    int pt = 0, ptB1 = 0;

    // for (int i=0; i<n; i++) {
    //     ll distTo1 = abs(a[i] - b1) + abs(b[i] - b1);
    //     toB1.emplace_back((distTo1 + a[i] + b[i] + 1) / 2, i);
    // }
    // sort(toB1.begin(), toB1.end());

    ll res = n; ll qtyb2 = 2*n;
    for (int i=0; i<n; i++) {
        res += a[i] + b[i];
        status[i] = 0;
    }

    for (; idxB2<2*n; idxB2++) {
        ll b2 = all[idxB2];
        // cout << b2 << ':' << '\n';
        while (pt < 2*n and (events[pt].x < b2 or (events[pt].x == b2 and events[pt].type == 0))) {
            int i = events[pt].i;
            if (status[i] == -1) {
                pt++;
                continue;
            }
            if (events[pt].type == 0) {
                res -= a[i] + b[i];
                res += b[i] - a[i];
                qtyb2-=2;
                status[i] = 1;
            } else {
                res -= b[i] - a[i];
                res += -a[i] - b[i];
                qtyb2 -= 2;
                status[i] = 2;
            }
            pt++;
        }
        // while (ptB1 < n and toB1[ptB1].first <= b2) {
        //     int i = toB1[ptB1].second;
        //     if (status[i] == 0) res -= a[i] + b[i];
        //     if (status[i] == 1) res -= b[i] - a[i];
        //     if (status[i] == 2) {
        //         res -= -a[i] - b[i];
        //         qtyb2 += 2;
        //     }
        //     res += abs(a[i] - b1) + abs(b[i] - b1);
        //     status[i] = -1;
        //     ptB1++;
        // }
        // cout << res << '\n';
        ans = min(ans, res - b2*qtyb2);
        while (pt < 2*n and events[pt].x == b2) {
            int i = events[pt].i;
            if (status[i] == -1) {
                pt++;
                continue;
            }
            res -= b[i] - a[i];
            res += -a[i] - b[i];
            qtyb2 -= 2;
            status[i] = 2;
            pt++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> k >> n;
    ll base = 0;
    for (int i=0; i<n; i++) {
        char side1, side2;
        cin >> side1 >> a[i] >> side2 >> b[i];
        if (side1 == side2) {
            base += abs(b[i] - a[i]);
            n--; i--;
            continue;
        }
        if (a[i] > b[i]) swap(a[i], b[i]);
        all[2*i] = a[i];
        all[2*i+1] = b[i];
        events[2*i] = Event(0, a[i], i);
        events[2*i+1] = Event(1, b[i], i);
    }
    sort(events, events+2*n, cmp);
    sort(all, all+2*n);

    k = min(k, n);
    if (k == 1) {
        solve(0);
    } else {
        for (int idxB1=0; idxB1 < 2*n-1; idxB1++) {
            b1 = all[idxB1];
            solve(idxB1+1);
        }
    }
    cout << base + ans << '\n';

    return 0;
}

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