| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 39521 | qoo2p5 | Palembang Bridges (APIO15_bridge) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 123;
const ll LINF = (ll) 1e18 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int) (x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
bool maxi(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
void run();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
run();
return 0;
}
const int N = (int) 1e5 + 123;
struct Fenwick {
unordered_map<int, ll> f;
void Fenwick() {
f.reserve(4 * N * 20);
}
void add(int x, ll y) {
x++;
for (; x < INF; x += x & (-x)) {
f[x] += y;
}
}
ll get(int r) {
ll res = 0;
r++;
for (; r > 0; r -= r & (-r)) {
if (f.count(r)) res += f[r];
}
return res;
}
void clear() {
for (auto &it : f) it.second = 0;
}
};
int k, n;
vector<pair<ll, ll>> a;
vector<ll> cool;
ll total;
ll pref[N], suff[N];
void solve1() {
vector<ll> p;
{
for (auto &it : a) {
p.pb(it.first);
p.pb(it.second);
}
sort(all(p));
}
int k = sz(p) / 2;
ll x = p[k];
ll ans = 0;
for (ll y : p) ans += abs(x - y);
ans += total;
cout << ans << "\n";
}
ll solve() {
sort(all(a), [] (const pair<ll, ll> &x, const pair<ll, ll> &y) {
return x.first + x.second < y.first + y.second;
});
Fenwick f_sum, f_cnt;
{
f_sum.clear();
f_cnt.clear();
multiset<ll> p, q;
ll sum = 0;
ll cnt = 0;
rep(i, 0, n) {
f_sum.add(a[i].first, a[i].first);
f_cnt.add(a[i].first, 1);
f_sum.add(a[i].second, a[i].second);
f_cnt.add(a[i].second, 1);
sum += a[i].first + a[i].second;
cnt += 2;
q.insert(a[i].first);
q.insert(a[i].second);
while (sz(q) > i + 1) {
ll el = *q.rbegin();
q.erase(q.find(el));
p.insert(el);
}
assert(sz(q) == sz(p));
while (*q.rbegin() > *p.begin()) {
ll x = *q.rbegin();
ll y = *p.begin();
q.erase(q.find(x));
q.insert(y);
p.erase(p.find(y));
p.insert(x);
}
ll mid = *q.rbegin();
ll sum_l = f_sum.get(mid);
ll sum_r = sum - sum_l;
ll cnt_l = f_cnt.get(mid);
ll cnt_r = cnt - cnt_l;
pref[i] = (mid * cnt_l - sum_l) + (sum_r - mid * cnt_r);
}
}
{
f_sum.clear();
f_cnt.clear();
multiset<ll> p, q;
ll sum = 0;
ll cnt = 0;
per(i, n - 1, 0) {
f_sum.add(a[i].first, a[i].first);
f_cnt.add(a[i].first, 1);
f_sum.add(a[i].second, a[i].second);
f_cnt.add(a[i].second, 1);
sum += a[i].first + a[i].second;
cnt += 2;
q.insert(a[i].first);
q.insert(a[i].second);
while (sz(q) > n - i) {
ll el = *q.rbegin();
q.erase(q.find(el));
p.insert(el);
}
assert(sz(q) == sz(p));
while (*q.rbegin() > *p.begin()) {
ll x = *q.rbegin();
ll y = *p.begin();
q.erase(q.find(x));
q.insert(y);
p.erase(p.find(y));
p.insert(x);
}
ll mid = *q.rbegin();
ll sum_l = f_sum.get(mid);
ll sum_r = sum - sum_l;
ll cnt_l = f_cnt.get(mid);
ll cnt_r = cnt - cnt_l;
suff[i] = (mid * cnt_l - sum_l) + (sum_r - mid * cnt_r);
}
}
ll ans = suff[0];
rep(i, 0, n) {
mini(ans, pref[i] + suff[i + 1]);
}
return ans;
}
void run() {
cin >> k >> n;
rep(i, 0, n) {
char t1, t2;
ll x1, x2;
cin >> t1 >> x1 >> t2 >> x2;
if (t1 == t2) {
total += abs(x1 - x2);
} else {
if (x1 > x2) {
swap(t1, t2);
swap(x1, x2);
}
a.pb({x1, x2});
cool.pb(x1);
cool.pb(x2);
}
}
sort(all(cool));
cool.resize(unique(all(cool)) - cool.begin());
sort(all(a));
n = sz(a);
total += n;
if (k == 1) {
solve1();
return;
}
if (n == 0) {
cout << total << "\n";
return;
}
ll ans = solve();
ans += total;
cout << ans << "\n";
}