이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) {
vector<array<int, 2>> points;
for (auto i : r) {
points.push_back({i, -1});
}
for (auto i : b) {
points.push_back({i, 1});
}
sort(points.begin(), points.end());
int origin_slope = 0, min_slope = 0, max_slope = 0;
int x_prv = 0, origin = 0;
map<int, int> slopes;
long long ans = 0;
for (auto [x, t] : points) {
slopes[origin] += 2 * (x - x_prv);
origin_slope += x - x_prv;
min_slope -= x - x_prv;
max_slope += x - x_prv;
x_prv = x;
if (t == -1) {
while (min_slope < 0) {
auto it = slopes.begin();
if (it->second > -min_slope) {
it->second += min_slope;
min_slope = 0;
} else {
min_slope += it->second;
slopes.erase(it);
}
}
origin_slope -= slopes[origin--];
ans -= origin_slope;
} else {
while (max_slope > 0) {
auto it = --slopes.end();
if (it->second > max_slope) {
it->second -= max_slope;
max_slope = 0;
} else {
max_slope -= it->second;
slopes.erase(it);
}
}
ans += origin_slope;
origin_slope += slopes[++origin];
}
}
return ans;
}
# | 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... |