이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())
template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
template<class... Args>
vec(size_t n = 0, Args... args)
: vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
template<class... Args>
vec(Args... args)
: vector<T>(args...) {}
};
template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
template<class T>
struct BIT {
vec<T, 1> a;
bool reversed;
BIT(int n, bool t_reversed = false)
: a(n),
reversed(t_reversed) {}
template<class U>
void Add(int i, U value) {
for (i = reversed ? SZ(a) - 1 - i : i; i < SZ(a); i |= i + 1) {
a[i] += value;
}
}
T Get(int i) const {
T ret{};
for (i = reversed ? SZ(a) - 1 - i : i; ~i; i = (i & (i + 1)) - 1) {
ret += a[i];
}
return ret;
}
template<class U>
void AddPosition(int i, U value) {
Add(i, value);
}
T GetRange(int l, int r) const { return Get(r) - Get(l - 1); }
template<class U>
void AddRange(int l, int r, U value) {
Add(l, value);
Add(r + 1, -value);
}
T GetPosition(int i) const {
return Get(i);
}
int LowerBound(T value) const {
return UpperBound(value - 1);
}
int UpperBound(T value) const {
int ret = 0;
for (int i = __lg(SZ(a)); ~i; --i) {
ret ^= 1 << i;
if (ret <= SZ(a) && value >= a[ret - 1]) {
value -= a[ret - 1];
} else {
ret ^= 1 << i;
}
}
return ret;
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n_citizens, n_bridges; cin >> n_bridges >> n_citizens;
int64_t answer = 0;
vec<pair<int, int>, 1> intervals;
vec<int, 1> xs;
while (n_citizens--) {
char source_zone, target_zone; int source_x, target_x; cin >> source_zone >> source_x >> target_zone >> target_x;
if (source_zone != target_zone) {
++answer;
intervals.emplace_back(min(source_x, target_x), max(source_x, target_x));
xs.emplace_back(intervals.back().first);
xs.emplace_back(intervals.back().second);
} else {
answer += abs(source_x - target_x);
}
}
sort(ALL(intervals), [&](const auto& i, const auto& j) {
return i.first + i.second < j.first + j.second;
});
sort(ALL(xs)); xs.erase(unique(ALL(xs)), xs.end());
BIT<int> bit_left_amount(SZ(xs)), bit_right_amount(SZ(xs));
BIT<int64_t> bit_left_sum(SZ(xs)), bit_right_sum(SZ(xs));
for (auto& interval : intervals) {
int index_x = static_cast<int>(lower_bound(ALL(xs), interval.first) - xs.begin());
bit_right_amount.Add(index_x, 1);
bit_right_sum.Add(index_x, interval.first);
index_x = static_cast<int>(lower_bound(ALL(xs), interval.second) - xs.begin());
bit_right_amount.Add(index_x, 1);
bit_right_sum.Add(index_x, interval.second);
}
int64_t result = numeric_limits<int64_t>::max();
auto Solve = [&]() {
int64_t ret = 0;
int amount = bit_left_amount.Get(SZ(xs) - 1),
index_x = bit_left_amount.LowerBound(amount >> 1);
ret += bit_left_sum.Get(SZ(xs) - 1) - (bit_left_sum.Get(index_x) << 1) + static_cast<int64_t>(xs[index_x]) * ((bit_left_amount.Get(index_x) << 1) - amount);
amount = bit_right_amount.Get(SZ(xs) - 1);
index_x = bit_right_amount.LowerBound(amount >> 1);
ret += bit_right_sum.Get(SZ(xs) - 1) - (bit_right_sum.Get(index_x) << 1) + static_cast<int64_t>(xs[index_x]) * ((bit_right_amount.Get(index_x) << 1) - amount);
Minimize(result, ret);
};
Solve();
if (n_bridges == 2) {
for (auto& interval : intervals) {
int index_x = static_cast<int>(lower_bound(ALL(xs), interval.first) - xs.begin());
bit_left_amount.Add(index_x, 1);
bit_left_sum.Add(index_x, interval.first);
bit_right_amount.Add(index_x, -1);
bit_right_sum.Add(index_x, -interval.first);
index_x = static_cast<int>(lower_bound(ALL(xs), interval.second) - xs.begin());
bit_left_amount.Add(index_x, 1);
bit_left_sum.Add(index_x, interval.second);
bit_right_amount.Add(index_x, -1);
bit_right_sum.Add(index_x, -interval.second);
Solve();
}
}
cout << answer + result << '\n';
return 0;
}
# | 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... |