| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 831774 | serifefedartar | Palembang Bridges (APIO15_bridge) | C++17 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 18
#define MAXN 200005
vector<pair<ll,ll>> seq;
int main() {
fast
ll K, N;
cin >> K >> N;
ll sum = 0;
for (int i = 0; i < N; i++) {
char ch1, ch2;
ll posR1, posR2;
cin >> ch1 >> posR1 >> ch2 >> posR2;
if (ch1 == ch2)
sum += abs(posR1 - posR2);
else
seq.push_back({min(posR1, posR2), max(posR1, posR2)});
}
sort(seq.begin(), seq.end(), [&](pair<int,int> a, pair<int,int> b) {
return a.f + a.s < b.f + b.s;
});
sum += seq.size();
if (seq.size() == 0) {
cout << sum << "\n";
return 0;
}
multiset<int> sR1, sR2, sL1, sL2;
ll sumR1 = 0, sumR2 = 0, sumL1 = 0, sumL2 = 0;
for (int i = 0; i < seq.size()/2; i++) {
sR1.insert(seq[i].f);
sR1.insert(seq[i].s);
sumR1 += seq[i].f + seq[i].s;
}
for (int i = seq.size()/2; i < (seq.size()/2) * 2; i++) {
sR2.insert(seq[i].f);
sR2.insert(seq[i].s);
sumR2 += seq[i].f + seq[i].s;
}
if (seq.size() % 2) {
sR1.insert(seq[seq.size()-1].f);
sR2.insert(seq[seq.size()-1].s);
sumR1 += seq[seq.size()-1].f;
sumR2 += seq[seq.size()-1].s;
}
while (*(--sR1.end()) > *(sR2.begin())) {
sR1.insert(*(sR2.begin()));
sumR1 += *(sR2.begin());
sumR2 -= *(sR2.begin());
sR2.erase(sR2.begin());
sR2.insert(*(--sR1.end()));
sumR2 += *(--sR1.end());
sumR1 -= *(--sR1.end());
sR1.erase(sR1.find(*(--sR1.end())));
}
ll median = *(--sR1.end());
ll ans = sR1.size()*median - sumR1 + sumR2 - sR2.size()*median + sum;
if (K == 2) {
for (int i = 0; i < seq.size() - 1; i++) {
ll val1 = seq[i].f;
ll val2 = seq[i].s;
if (sR1.count(val1)) {
sR1.erase(sR1.find(val1));
sumR1 -= val1;
} else {
sR2.erase(sR2.find(val1));
sumR2 -= val1;
}
if (sR1.count(val2)) {
sR1.erase(sR1.find(val2));
sumR1 -= val2;
} else {
sR2.erase(sR2.find(val2));
sumR2 -= val2;
}
sL1.insert(val1);
sL2.insert(val2);
sumL1 += val1;
sumL2 += val2;
while (sR1.size() > sR2.size()) {
sR2.insert(*(--sR1.end()));
sumR2 += *(--sR1.end());
sumR1 += *(--sR1.end());
sR1.erase(sR1.find(*(--sR1.end())));
}
while (sR2.size() > sR1.size()) {
sR1.insert(*(sR2.begin()));
sumR1 += *(sR2.begin());
sumR2 -= *(sR2.begin());
sR2.erase(sR2.begin());
}
while (sL1.size() > sL2.size()) {
sL2.insert(*(--sL1.end()));
sumL2 += *(--sL1.end());
sumL1 += *(--sL1.end());
sL1.erase(sL1.find(*(--sL1.end())));
}
while (sL2.size() > sL1.size()) {
sL1.insert(*(sL2.begin()));
sumL1 += *(sL2.begin());
sumL2 -= *(sL2.begin());
sL2.erase(sL2.begin());
}
while (*(--sR1.end()) > *(sR2.begin())) {
sR1.insert(*(sR2.begin()));
sumR1 += *(sR2.begin());
sumR2 -= *(sR2.begin());
sR2.erase(sR2.begin());
sR2.insert(*(--sR1.end()));
sumR2 += *(--sR1.end());
sumR1 -= *(--sR1.end());
sR1.erase(sR1.find(*(--sR1.end())));
}
while (*(--sL1.end()) > *(sL2.begin())) {
sL1.insert(*(sL2.begin()));
sumL1 += *(sL2.begin());
sumL2 -= *(sL2.begin());
sL2.erase(sL2.begin());
sL2.insert(*(--sL1.end()));
sumL2 += *(--sL1.end());
sumL1 -= *(--sL1.end());
sL1.erase(sL1.find(*(--sL1.end())));
}
ll median1 = *(--sR1.end());
ll median2 = *(--sL1.end());
ans = min(ans, sR1.size()*median1 - sumR1 + sumR2 - sR2.size()*median1 + sum
+ sL1.size()*median2 - sumL1 + sumL2 - sL2.size()*median2);
}
}
cout << ans << "\n";
}