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>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b ; --i)
#define REP(i, a) for (int i = 0, _a = (a); i < _a; ++i)
#define pp pair<long long, long long>
#define bit(S, i) (((S) >> i) & 1)
#define next __next
#define prev __prev
#define N 1000030
using namespace std;
int n, m, x1[N], x2[N];
vector<long long> ranking;
vector<pp> e;
priority_queue<long long> BottomMax;
priority_queue<long long, vector<long long>, greater<long long> > TopMin;
long long Left[N], Right[N];
void Solve() {
while (!BottomMax.empty()) BottomMax.pop();
while (!TopMin.empty()) TopMin.pop();
// Median is top of BottomMax
long long Low = 0, High = 0;
REP(i, n) {
BottomMax.push(x1[e[i].second]);
BottomMax.push(x2[e[i].second]);
Low += x1[e[i].second];
Low += x2[e[i].second];
while (BottomMax.size() - TopMin.size() > 1) {
TopMin.push(BottomMax.top());
Low -= BottomMax.top();
High += BottomMax.top();
BottomMax.pop();
if (!BottomMax.empty() && TopMin.top() < BottomMax.top()) {
BottomMax.push(TopMin.top());
Low += TopMin.top();
High -= TopMin.top();
TopMin.pop();
}
}
Right[i] = BottomMax.top() * BottomMax.size() - Low
+ High - BottomMax.top() * TopMin.size();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int k;
cin >> k >> n;
long long init = 0;
FOR(i, 1, n) {
char label1, label2;
cin >> label1 >> x1[i] >> label2 >> x2[i];
if (x1[i] > x2[i]) swap(x1[i], x2[i]);
if (label1 == label2) {
init += x2[i] - x1[i];
}
else {
e.push_back(pp(x1[i] + x2[i], i));
ranking.push_back(x1[i]);
ranking.push_back(x2[i]);
init++;
}
}
//Initialization
sort(ranking.begin(), ranking.end());
ranking.resize(unique(ranking.begin(), ranking.end()) - ranking.begin());
n = e.size();
sort(e.begin(), e.end());
m = ranking.size();
// Cal median from Left to Right
Solve();
REP(i, n) Left[i] = Right[i];
// Cal median from Right to Left
reverse(e.begin(), e.end());
Solve();
reverse(Right, Right + n);
if (k == 1) cout << Left[n - 1] + init;
else {
long long best = Right[0];
REP(i, n - 1) best = min(best, Left[i] + Right[i + 1]);
cout << best + init;
}
}
# | 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... |