Submission #1288193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288193		gustavo_d	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	61 ms	9916 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;

vector<ll> a, b, all;
vector<Event> events;
vector<pair<ll, int>> toB1;
vector<int> status;

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.at(i) - b1) + abs(b.at(i) - b1);
    //     toB1.emplace_back((distTo1 + a.at(i) + b.at(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.at(i) + b.at(i);
        status.at(i) = 0;
    }

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

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

    cin >> k >> n;
    a = vector<ll>(n);
    b = vector<ll>(n);
    status = vector<int>(n);
    ll base = 0;
    for (int i=0; i<n; i++) {
        char side1, side2;
        cin >> side1 >> a.at(i) >> side2 >> b.at(i);
        if (side1 == side2) {
            base += abs(b.at(i) - a.at(i));
            n--; i--;
            continue;
        }
        if (a.at(i) > b.at(i)) swap(a.at(i), b.at(i));
        all.push_back(a.at(i));
        all.push_back(b.at(i));
        events.push_back(Event(0, a.at(i), i));
        events.push_back(Event(1, b.at(i), i));
    }
    sort(events.begin(), events.end(), cmp);
    sort(all.begin(), all.end());

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

    return 0;
}

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