This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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.count(val))
{
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)
| ~~~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |