Submission #1155354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155354		tset	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	65 ms	6072 KiB

bridge

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

#define int long long

bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first + a.second < b.first + b.second;
}

int sumL, sumR;
priority_queue<int> pqL, pqR;
void insert(int x)
{
    if(pqL.empty() || x <= pqL.top())
    {
        pqL.push(x);
        sumL += x;
    }
    else
    {
        pqR.push(-x);
        sumR += x;
    }
    while(pqL.size() < pqR.size())
    {
        int t = -pqR.top();
        pqR.pop();
        pqL.push(t);
        sumL += t;
        sumR -= t;
    }
    while(pqL.size() > pqR.size() + 1)
    {
        int t = pqL.top();
        pqL.pop();
        pqR.push(-t);
        sumL -= t;
        sumR += t;
    }
}

signed main()
{
    int K, N;
    int bonus = 0;
    scanf("%lld %lld\n", &K, &N);
    vector<pair<int, int>> inters;
    for(int i = 0; i < N; i++)
    {
        char c1, c2;
        int x, y;
        scanf("%c %lld %c %lld\n", &c1, &x, &c2, &y);
        if(c1 == c2)
            bonus += abs(x - y);
        else
        {
            inters.push_back({min(x, y), max(x, y)});
            bonus ++;
        }
    }
    sort(inters.begin(), inters.end(), cmp);
    sumL = 0, sumR = 0;
    N = inters.size();
    if(N == 0)
    {
        printf("%lld\n", bonus);
        return 0;
    }
    vector<int> prefix(N);
    for(int i = 0; i < N; i++)
    {
        insert(inters[i].first);
        insert(inters[i].second);
        //printf("[%lld, %lld]\n", inters[i].first, inters[i].second);
        //printf("%lld %lld\n", sumL, sumR);
        prefix[i] = sumR-sumL;
    }
    int ans =  bonus + prefix[N-1];
    if(K == 1)
    {
        printf("%lld\n", ans);
        return 0;
    }
    sumL = 0, sumR = 0;
    while(!pqL.empty()) pqL.pop();
    while(!pqR.empty()) pqR.pop();
    for(int i = N-1; i > 0; i--)
    {
        insert(inters[i].first);
        insert(inters[i].second);
        ans = min(ans, bonus + prefix[i-1] + sumR - sumL);
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%lld %lld\n", &K, &N);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%c %lld %c %lld\n", &c1, &x, &c2, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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