Submission #1156143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156143		raphaelp	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	128 ms	12016 KiB

bridge

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

int main()
{
    long long K, N;
    cin >> K >> N;

    long long tot = 0;
    vector<vector<long long>> Tab;
    long long buff = 0;
    for (long long i = 0; i < N; i++)
    {
        long long b, d;
        char a, c;
        cin >> a >> b >> c >> d;
        tot += abs(b - d);
        if (a == c)
        {
            continue;
        }
        Tab.push_back({b + d, min(b, d), max(b, d)});
        buff++;
        tot++;
    }
    long long add = 0;
    sort(Tab.begin(), Tab.end());
    vector<long long> ans(buff);
    N = buff;
    priority_queue<pair<long long, long long>> left, right;
    left.push({-1000000000, 0});
    right.push({-1000000000, 0});
    long long cur = 0, rig = 0;
    for (long long i = 0; i < N; i++)
    {
        if (Tab[i][1] < left.top().first)
            left.push({Tab[i][1], 0});
        else
        {
            right.push({-Tab[i][1], 0});
            add += (Tab[i][1] - left.top().first) * 2;
            rig++;
        }
        right.push({-Tab[i][2], 1});
        if (right.size() > left.size())
        {
            add += (-right.top().first - left.top().first) * (cur - rig) * 2;
            left.push({-right.top().first, right.top().second});
            if (right.top().second == 0)
                rig--;
            else
                cur++;
            right.pop();
        }
        ans[i] = add;
    }
    while (left.size())
        left.pop();
    while (right.size())
        right.pop();
    cur = 0, rig = 0, add = 0;
    left.push({-1000000000, 0});
    right.push({-1000000000, 0});
    for (long long i = N - 1; i > 0; i--)
    {
        if (Tab[i][2] > -left.top().first)
            left.push({-Tab[i][2], 0});
        else
        {
            right.push({Tab[i][2], 0});
            add += (-left.top().first - Tab[i][2]) * 2;
            rig++;
        }
        right.push({Tab[i][1], 1});
        if (right.size() > left.size())
        {
            add += (-right.top().first - left.top().first) * (cur - rig) * 2;
            left.push({-right.top().first, right.top().second});
            if (right.top().second == 0)
                rig--;
            else
                cur++;
            right.pop();
        }
        ans[i - 1] += add;
    }
    if (N == 0)
    {
        cout << tot;
        return 0;
    }
    if (K == 1)
    {
        cout << tot + ans[N - 1];
        return 0;
    }
    long long minn = ans[0];
    for (long long i = 0; i < N; i++)
        minn = min(minn, ans[i]);
    cout << tot + minn;
}

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