Submission #935102

#	Time	Username	Problem	Language	Result	Execution time	Memory
935102		LonlyR	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	60 ms	7880 KiB

bridge

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e5 + 5;
int n, same, k, sumn, sumx, cur;
int pref[maxn];
vector<pair<int,int>> points;
priority_queue<int> mn;
priority_queue<int, vector<int>, greater<int>> mx;

inline void amn(int x)
{
    mn.emplace(x);
    sumn += x;
}

inline void amx(int x)
{
    mx.emplace(x);
    sumx += x;
}

inline void popn()
{
    sumn -= mn.top();
    mn.pop();
}

inline void popx()
{
    sumx -= mx.top();
    mx.pop();
}

inline void add(int x)
{
    if (mn.size() == mx.size()) /// to the small one :p
    {
        if (mn.empty())
            amn(x);
        else
        {
            vector<int> tmp = {x, mn.top(), mx.top()};
            popn(); popx();
            sort(tmp.begin(), tmp.end());
            amn(tmp[0]);
            amn(tmp[1]);
            amx(tmp[2]);
        }
    }
    else
    {
        if (mx.empty())
        {
            vector<int> tmp = {mn.top(), x};
            popn();
            sort(tmp.begin(), tmp.end());
            amn(tmp[0]);
            amx(tmp[1]);
        }
        else
        {
            vector<int> tmp = {x, mn.top(), mx.top()};
            popn(); popx();
            sort(tmp.begin(), tmp.end());
            amn(tmp[0]);
            amx(tmp[1]);
            amx(tmp[2]);
        }
    }
    if (mn.size() == mx.size())
    {
        int median = (mn.top() + mx.top()) / 2;
        cur = sumx - sumn;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> k >> n;
    for (int i = 1; i <= n; i++)
    {
        char side1, side2;
        int x, y;
        cin >> side1 >> x >> side2 >> y;
        if (side1 == side2) same += abs(x - y);
        else points.emplace_back(x, y);
    }
    n = points.size();
    for (int i = 0; i < n; i++)
    {
        add(points[i].first);
        add(points[i].second);
        pref[i] = cur;
    }
    if (k == 1) return cout << pref[n - 1] + n + same, 0;
    int ans = pref[n - 1];
    while (mn.size()) popn();
    while (mx.size()) popx();
    for (int i = n - 1; i >= 1; i--)
    {
        add(points[i].first);
        add(points[i].second);
        ans = min(ans, pref[i - 1] + cur);
    }
    cout << ans + n + same;
}

Compilation message (stderr)

bridge.cpp: In function 'void add(long long int)':
bridge.cpp:74:13: warning: unused variable 'median' [-Wunused-variable]
   74 |         int median = (mn.top() + mx.top()) / 2;
      |             ^~~~~~

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