Submission #39504

#TimeUsernameProblemLanguageResultExecution timeMemory
39504qoo2p5Palembang Bridges (APIO15_bridge)C++14
63 / 100
2000 ms10416 KiB
#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; int k, n; vector<pair<ll, ll>> a; vector<ll> cool; ll total; 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 f(ll x1, ll x2) { ll cur = 0; for (auto &it : a) { ll best = LINF; mini(best, abs(it.first - x1) + abs(it.second - x1)); mini(best, abs(it.first - x2) + abs(it.second - x2)); cur += best; } return cur; }; struct Q { int l, r, tl, tr; }; ll solve() { vector<Q> q, nq; q.pb({0, sz(cool), 0, sz(cool)}); ll res = LINF; while (sz(q)) { for (auto &it : q) { int l = it.l; int r = it.r; int tl = it.tl; int tr = it.tr; int mid = (l + r) / 2; ll ans = LINF; int opt = tl; rep(i, tl, min(mid + 1, tr)) { if (mini(ans, f(cool[i], cool[mid]))) { opt = i; } } if (l < mid) { nq.pb({l, mid, tl, opt + 1}); } if (mid + 1 < r) { nq.pb({mid + 1, r, opt, tr}); } mini(res, ans); } swap(q, nq); nq.clear(); } return res; } 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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...