Submission #1257564

#TimeUsernameProblemLanguageResultExecution timeMemory
1257564xardkodychPalembang Bridges (APIO15_bridge)C++20
22 / 100
32 ms3772 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 int k, n; int s[N], t[N]; bool f[N]; int calc(int x) { int ans = 0; for (int i = 0; i < n; i++) { if (f[i]) { ans += abs(s[i] - x) + abs(t[i] - x) + 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; } if (k == 1) { sort(all(pos)); pos.resize(unique(all(pos)) - pos.begin()); int l = 0, r = (int) pos.size() - 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'; } }
#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...