Submission #1103703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103703		MongHwa	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	265 ms	14368 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

#define ll long long

struct A {
    ll sum, s, t;

    bool operator< (A& other) {
        return sum < other.sum;
    }
};

vector<A> arr;
multiset<int> lo1, hi1, lo2, hi2;

void Ins(multiset<int>& lo, multiset<int>& hi, ll& losum, ll& hisum, int val, int sz)
{
    if(!lo.empty() && *lo.rbegin() < val)
    {
        hisum += val;
        hi.insert(val);
    }
    else
    {
        losum += val;
        lo.insert(val);
    }
    
    int mid = sz/2 + (sz%2 > 0);
    if(!hi.empty() && hi.size() > sz/2)
    {
        losum += *hi.begin();
        hisum -= *hi.begin();
        lo.insert(*hi.begin());
        hi.erase(hi.begin());
    }
    else if(!lo.empty() && lo.size() > mid)
    {
        losum -= *lo.rbegin();
        hisum += *lo.rbegin();
        hi.insert(*lo.rbegin());
        lo.erase(prev(lo.end()));
    }
}

void Del(multiset<int>& lo, multiset<int>& hi, ll& losum, ll& hisum, int val, int sz)
{
    if(lo.find(val) != lo.end())
    {
        losum -= val;
        lo.erase(lo.find(val));
    }
    else
    {
        hisum -= val;
        hi.erase(hi.find(val));
    }
    
    int mid = sz/2 + (sz%2 > 0);
    if(!hi.empty() && hi.size() > sz/2)
    {
        losum += *hi.begin();
        hisum -= *hi.begin();
        lo.insert(*hi.begin());
        hi.erase(hi.begin());
    }
    else if(!lo.empty() && lo.size() > mid)
    {
        losum -= *lo.rbegin();
        hisum += *lo.rbegin();
        hi.insert(*lo.rbegin());
        lo.erase(prev(lo.end()));
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int k, n;
    cin >> k >> n;

    ll ans = 0;
    ll losum1 = 0, hisum1 = 0, losum2 = 0, hisum2 = 0;
    for(int i = 0; i < n; i++)
    {
        char p, q; int s, t;
        cin >> p >> s >> q >> t;

        if(p == q)
            ans += abs(s-t);
        else
        {
            arr.push_back({s+t, s, t});
            Ins(lo2, hi2, losum2, hisum2, s, arr.size()*2);
            Ins(lo2, hi2, losum2, hisum2, t, arr.size()*2);
        }
    }

    if(arr.empty())
    {
        cout << ans << '\n';
        return 0;
    }

    if(arr.size() == 1 || k == 1)
    {
        ll mid = *lo2.rbegin();
        cout << ans + (mid*lo2.size() - losum2) + (hisum2 - mid*hi2.size()) + arr.size() << '\n';

        return 0;
    }

    sort(arr.begin(), arr.end());

    ll val = 1e18;
    for(int i = 0; i < (int)arr.size()-1; i++)
    {
        Ins(lo1, hi1, losum1, hisum1, arr[i].s, (i+1)*2);
        Ins(lo1, hi1, losum1, hisum1, arr[i].t, (i+1)*2);
        
        Del(lo2, hi2, losum2, hisum2, arr[i].s, arr.size()*2 - (i+1)*2);
        Del(lo2, hi2, losum2, hisum2, arr[i].t, arr.size()*2 - (i+1)*2);

        ll mid = *lo1.rbegin();
        ll elem1 = (mid*lo1.size() - losum1) + (hisum1 - mid*hi1.size());
        mid = *lo2.rbegin();
        ll elem2 = (mid*lo2.size() - losum2) + (hisum2 - mid*hi2.size());

        val = min(val, elem1 + elem2);
    }

    cout << ans + val + arr.size() << '\n';
}

Compilation message (stderr)

bridge.cpp: In function 'void Ins(std::multiset<int>&, std::multiset<int>&, long long int&, long long int&, int, int)':
bridge.cpp:34:33: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(!hi.empty() && hi.size() > sz/2)
      |                       ~~~~~~~~~~^~~~~~
bridge.cpp:41:38: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     else if(!lo.empty() && lo.size() > mid)
      |                            ~~~~~~~~~~^~~~~
bridge.cpp: In function 'void Del(std::multiset<int>&, std::multiset<int>&, long long int&, long long int&, int, int)':
bridge.cpp:64:33: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     if(!hi.empty() && hi.size() > sz/2)
      |                       ~~~~~~~~~~^~~~~~
bridge.cpp:71:38: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     else if(!lo.empty() && lo.size() > mid)
      |                            ~~~~~~~~~~^~~~~

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