Submission #1257575

#TimeUsernameProblemLanguageResultExecution timeMemory
1257575xardkodychPalembang Bridges (APIO15_bridge)C++20
22 / 100
36 ms3776 KiB
// #pragma optimize("Ofast") #include "bits/stdc++.h" #define int long long #define all(v) (v).begin(), (v).end() #define pb push_back #define em emplace_back #define mp make_pair #define F first #define S second using namespace std; template<class C> using vec = vector<C>; using vi = vector<int>; using vpi = vector<pair<int, int>>; using pii = pair<int, int>; #ifdef LOCAL const int N = 15; #else const int N = 100001; #endif const int inf = (int) 1e11; int k, n; int s[N], t[N]; bool f[N]; int calc(int x, int y = inf) { int ans = 0; for (int i = 0; i < n; i++) { if (f[i]) { ans += min(abs(s[i] - x) + abs(t[i] - x) + 1, abs(s[i] - y) + abs(t[i] - y) + 1); } else { ans += abs(s[i] - t[i]); } } return ans; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> k >> n; vi pos; for (int i = 0; i < n; i++) { char a, b; cin >> a >> s[i] >> b >> t[i]; pos.pb(s[i]); pos.pb(t[i]); f[i] = a!=b; } sort(all(pos)); pos.resize(unique(all(pos)) - pos.begin()); int m = (int) pos.size(); if (k == 1) { int l = 0, r = m - 1; while (l + 1 < r) { int mid = (l + r) >> 1; if (calc(pos[mid]) < calc(pos[mid + 1])) r = mid; else l = mid; } int ans = LLONG_MAX; for (int i = l; i <= r; i++) ans = min(ans, calc(pos[i])); cout << ans << '\n'; } if (k == 2) { auto Bebra = [&](int x) { int l = x+1, r = m - 1; while (l + 1 < r) { int mid = (l + r) >> 1; if (calc(pos[x], pos[mid]) < calc(pos[x], pos[mid+1])) { r = mid; } else { l = mid; } } int ans = LLONG_MAX; for (int i = l; i <= r; i++) ans = min(ans, calc(pos[x], pos[i])); return ans; }; int l = 0, r = m - 1; while (l + 1 < r) { int mid = (l + r) >> 1; if (Bebra(mid) < Bebra(mid+1)) r = mid; else l = mid; } int ans = LLONG_MAX; for (int i = l; i <= r; i++) ans = min(ans, Bebra(i)); 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...