Submission #1055126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055126		Harold	Palembang Bridges (APIO15_bridge)	C++14	78 / 100	96 ms	8040 KiB

bridge

// TST
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5+10;

vector<pair<ll, ll>> points;
ll pref[MAXN];

priority_queue<ll> pqLeft;
priority_queue<ll, vector<ll>, greater<ll>> pqRight;
ll sumLeft = 0, sumRight = 0;

void ins(ll x) {
    if (pqLeft.empty() || pqLeft.top() >= x) {
        pqLeft.push(x);
        sumLeft += x;
    } else {
        pqRight.push(x);
        sumRight += x;
    }

    if (pqRight.size() > pqLeft.size()) {
        ll t = pqRight.top();
        pqRight.pop();
        sumRight -= t;
        pqLeft.push(t);
        sumLeft += t;
    } else if (pqLeft.size() > pqRight.size() + 1) {
        ll t = pqLeft.top();
        pqLeft.pop();
        sumLeft -= t;
        pqRight.push(t);
        sumRight += t;
    }
}

ll getSumOfDistances() {
    return sumRight - sumLeft;
}

void clearPq() {
    while(pqLeft.size() > 0) {pqLeft.pop();}
    while(pqRight.size() > 0) {pqRight.pop();}

    sumLeft = sumRight = 0;
}

int main() {
    int k, n;

    cin >> k >> n;
    ll sumOfSame = 0;

    for (int i = 0; i < n; i++) {
        char p, q;
        ll s, t;
        cin >> p >> s >> q >> t;
        if(p == q) sumOfSame += abs(s - t);
        else points.push_back({s, t});
    }

    sort(points.begin(), points.end(), [](pair<ll, ll> a, pair<ll, ll> b) {
            return a.first + a.second < b.first + b.second;
        });

    int a = points.size();
    for (int i = 0; i < a; i++) {
        auto p = points[i];
        ll s = p.first;
        ll t = p.second;

        ins(s);
        ins(t);
        pref[i] = getSumOfDistances();
    }

    if (k == 1) {
        ll ats;
        if (a == 0) {
            ats = sumOfSame;
        } else {
            ll ats = sumOfSame + pref[a-1] + a;
        }
        cout << ats << endl;
        return 0;
    }

    ll ats = a > 0 ? pref[a-1] : 0;
    clearPq();
    for (int i = a-1; i > 0; i--) {
        auto p = points[i];
        ll s = p.first;
        ll t = p.second;

        ins(s);
        ins(t);
        ll dabAts = getSumOfDistances() + pref[i-1];
        ats = min(dabAts, ats);
    }

    ats += a + sumOfSame;
    cout << ats << endl;

    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:86:16: warning: unused variable 'ats' [-Wunused-variable]
   86 |             ll ats = sumOfSame + pref[a-1] + a;
      |                ^~~

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