Submission #1250977

#TimeUsernameProblemLanguageResultExecution timeMemory
1250977thuhiennePalembang Bridges (APIO15_bridge)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define FastIO ios_base::sync_with_stdio(0);cin.tie(nullptr); #define MULTEST int tt;cin >> tt;while (tt--) solve(); int k,n,cnt; long long offset = 0; pair <int,int> segment[100009]; namespace sub1 { bool check() { return k == 1 && n <= 1000; } long long cal(int point) { long long ret = 0; for (int i = 1;i <= n;i++) { ret += abs(segment[i].first - point) + abs(segment[i].second - point); } return ret; } void solve() { long long curr = 1e18; for (int i = 1;i <= n;i++) { curr = min({curr,cal(segment[i].first),cal(segment[i].second)}); } cout << curr + offset; } } namespace sub2 { bool check() { return k == 1 && n <= 100000; } int points[200009]; long long ans[200009],ans2[200009]; void solve() { long long total = 0; for (int i = 1;i <= n;i++) { points[i] = segment[i].first; points[i + n] = segment[i].second; total += segment[i].second - segment[i].first; } sort(points + 1,points + 1 + 2*n); sort(segment + 1,segment + 1 + n,[] (pair <int,int> a,pair <int,int> b) { return a.second < b.second; }); long long curr = 0,curr2 = 0; int pt = 0; for (int i = 1;i <= 2*n;i++) { while (pt < n && segment[pt + 1].second < points[i]) { pt++; curr2 += segment[pt].second - segment[pt].first; curr += segment[pt].second + segment[pt].first; } ans2[i] += curr2; ans[i] += 2ll*pt*points[i] - curr; } sort(segment + 1,segment + 1 + n,[] (pair <int,int> a,pair <int,int> b) { return a.first < b.first; }); curr = curr2 = 0; pt = n + 1; for (int i = 2*n;i >= 1;i--) { while (pt > 1 && segment[pt - 1].first > points[i]) { pt--; curr2 += segment[pt].second - segment[pt].first; curr += segment[pt].second + segment[pt].first; } ans2[i] += curr2; ans[i] += curr - 2ll*(n - pt + 1)*points[i]; } long long ret = 1e18; for (int i = 1;i <= 2*n;i++) { ret = min(ret,ans[i] + total - ans2[i]); } cout << ret + offset; } } namespace sub3 { bool check() { return k == 2 && n <= 100; } int pt[209]; long long cal(int point,int point2) { long long ret = 0; for (int i = 1;i <= n;i++) { ret += min({abs(segment[i].first - point) + abs(segment[i].second - point), abs(segment[i].first - point2) + abs(segment[i].second - point2)}); } return ret; } void solve() { long long curr = 1e18; for (int i = 1;i <= n;i++) { pt[i] = segment[i].first; pt[i + n] = segment[i].second; } for (int i = 1;i <= 2*n;i++) { for (int j = i + 1;j <= 2*n;j++) { curr = min(curr,cal(pt[i],pt[j])); } } cout << curr + offset; } } int main() { // FastIO // MULTEST // freopen("bridges.inp","r",stdin); // freopen("bridges.out","w",stdout); cin >> k >> n; for (int i = 1;i <= n;i++) { char _1,_2;int __1,__2; cin >> _1 >> __1 >> _2 >> __2; if (_1 == _2) offset += abs(__2 - __1); else { segment[++cnt] = {__1,__2}; offset++; if (segment[cnt].first > segment[cnt].second) swap(segment[cnt].first,segment[cnt].second); } } n = cnt; if (sub1::check()) { sub1::solve(); return 0; } if (sub2::check()) { sub2::solve(); return 0; } if (sub3::check()) { sub3::solve(); return 0; } } /* Nho doi vai em gay co gai ay ngoi duoi goc pho nen tho ... */
#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...