#include<bits/stdc++.h>
#define debug(v) //cerr << #v << ": " << v << '\n';
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int k, n;
ll ans;
vector<pii> inter;
bool cmp(pii a, pii b){
return a.first+a.second < b.first+b.second;
}
struct two_set{
multiset<int> s1, s2;
//s1-> smaller than mid
//s2 -> greater than mid;
//s1.size() >= s2.size();
ll sum1, sum2;
ll median(){
if(s1.empty()){
// cerr << "empty set\n";
return 0;
}
return *s1.rbegin();
}
void add(int v){
if(s1.empty()){
s1.insert(v);
sum1 += v;
return;
}
if(s1.size() == s2.size()){
if(v <= *s2.begin()){
sum1 += v;
s1.insert(v);
}
else{
sum1 += *s2.begin();
s1.insert( *s2.begin() );
sum2 -= *s2.begin();
s2.erase(s2.begin());
sum2 += v;
s2.insert(v);
}
}
else{
if(v <= *s1.rbegin()){
sum2 += *(--s1.end());
s2.insert( *(--s1.end()) );
sum1 -= *(--s1.end());
s1.erase( --s1.end() );
sum1 += v;
s1.insert(v);
}
else{
sum2 += v;
s2.insert(v);
}
}
}
void remove(int v){
if(s1.size() == s2.size()){
if(v <= *s1.rbegin()){
sum1 -= v;
s1.erase(s1.find(v));
sum1 += *s2.begin();
s1.insert(*s2.begin());
sum2 -= *s2.begin();
s2.erase(s2.begin());
}
else{
sum2 -= v;
s2.erase(s2.find(v));
}
}
else{
if(v <= *s1.rbegin()){
sum1 -= v;
s1.erase(s1.find(v));
}
else{
sum2 -= v;
s2.erase(s2.find(v));
sum2 += *(--s1.end()) ;
s2.insert( *(--s1.end()) );
sum1 -= *(--s1.end()) ;
s1.erase( --s1.end() );
}
}
}
ll dist(){
return s1.size()*median()-sum1 + sum2 - s2.size()*median();
}
};
two_set esq, dir;
int main(){
cin.tie(0)->sync_with_stdio(0);
int k, n;
cin >> k >> n;
for(int i = 1; i <= n; i++){
char za, zb;
int a, b;
cin >> za >> a >> zb >> b;
if(a>b) swap(a, b);
if(za==zb){
ans += b-a;
}
else{
ans++;
inter.push_back({a, b});
}
}
debug(ans)
sort(inter.begin(), inter.end());
for(auto[L, R] : inter){
dir.add(L);
dir.add(R);
debug(L);
debug(R);
debug(dir.median());
debug(dir.dist());
}
debug(dir.median());
if(k == 1){
cout << ans+dir.dist() << '\n';
return 0;
}
ll best = 1e18;
for(auto[L, R] : inter){
dir.remove(L);
dir.remove(R);
esq.add(L);
esq.add(R);
debug(dir.median());
debug(dir.dist());
debug(esq.median());
debug(esq.dist());
debug(' ');
best = min(best, dir.dist()+esq.dist());
}
debug(best)
cout << ans+best << '\n';
}
# | 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... |