이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
pp BIT[N];
vector<long long> ranking;
vector<pp> e;
void Up(int u, long long val) {
for (; u <= m; u += u & -u) {
BIT[u].first += val;
BIT[u].second++;
}
}
pp Get(int u) {
pp ans = pp(0, 0);
for (; u > 0; u -= u & -u) {
ans.first += BIT[u].first;
ans.second += BIT[u].second;
}
return ans;
}
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
FOR(i, 1, m) BIT[i] = pp(0, 0);// pair<Sum, counter>
long long total = 0;
REP(i, n) {
int pos = lower_bound(ranking.begin(), ranking.end(), x1[e[i].second]) - ranking.begin() + 1;
Up(pos, x1[e[i].second]);
pos = lower_bound(ranking.begin(), ranking.end(), x2[e[i].second]) - ranking.begin() + 1;
Up(pos, x2[e[i].second]);
total += e[i].first;
BottomMax.push(x1[e[i].second]);
BottomMax.push(x2[e[i].second]);
while (BottomMax.size() - TopMin.size() > 1) {
TopMin.push(BottomMax.top());
BottomMax.pop();
if (!BottomMax.empty() && TopMin.top() < BottomMax.top()) {
BottomMax.push(TopMin.top());
TopMin.pop();
}
}
int posMed = lower_bound(ranking.begin(), ranking.end(), BottomMax.top()) - ranking.begin() + 1;
pp lowerMed = Get(posMed);
Right[i] = ranking[posMed - 1] * lowerMed.second - lowerMed.first
+ total - lowerMed.first - ranking[posMed - 1] * (2 * i + 2 - lowerMed.second);
}
}
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... |