제출 #328624

#제출 시각아이디문제언어결과실행 시간메모리
328624Mahdi_ShokoufiPalembang Bridges (APIO15_bridge)C++17
100 / 100
420 ms21584 KiB
//In The Name of Allah #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair < int , int > pii; typedef pair < ll , ll > pll; #define X first #define Y second #define mp make_pair #define pb push_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x.size()) const int N = 1e5 + 10; const ll mod = 1e9 + 7; const ll inf = 1e9 + 10; ll P[2][N], ps[2][N], a[2][N], pre[N], suf[N]; vector < ll > vec; vector < pll > seg; bool cmp(pll x, pll y){ return (x.X + x.Y) < (y.X + y.Y); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, k, m = 1, ans = 0, EXT = 0; cin >> k >> n; for (ll i = 1; i <= n; i ++){ char c1, c2; ll x1, x2; cin >> c1 >> x1 >> c2 >> x2; if (c1 == c2) ans += abs(x1 - x2), EXT += abs(x1 - x2); else{ P[c1 - 'A'][m] = x1; P[c2 - 'A'][m] = x2; a[c1 - 'A'][m] = x1; a[c2 - 'A'][m] = x2; seg.pb(mp(x1, x2)); vec.pb(x1); vec.pb(x2); m ++; ans ++; } } P[0][m] = inf; P[1][m] = inf; vec.pb(inf); m ++; P[0][m] = inf + 1; P[1][m] = inf + 1; vec.pb(inf + 1); m ++; sort(P[0] + 1, P[0] + m); sort(P[1] + 1, P[1] + m); for (ll i = 1; i < m; i ++){ ps[0][i] = ps[0][i - 1] + P[0][i]; ps[1][i] = ps[1][i - 1] + P[1][i]; } vec.resize(unique(all(vec)) - vec.begin()); ll res = inf * inf; if (k == 1){ for (ll x : vec){ ll cost = 0; ll p1 = upper_bound(P[0] + 1, P[0] + m, x) - P[0]; ll p2 = upper_bound(P[1] + 1, P[1] + m, x) - P[1]; cost += (p1 - 1) * x - ps[0][p1 - 1]; cost += (p2 - 1) * x - ps[1][p2 - 1]; cost += ps[0][m - 3] - ps[0][p1 - 1] - x * (m - p1 - 2); cost += ps[1][m - 3] - ps[1][p2 - 1] - x * (m - p2 - 2); res = min(res, cost); } cout << ans + res; return 0; } if (seg.empty()) return cout << ans, 0; sort(all(seg), cmp); multiset < ll > mnH, mxH; ll mnS = 0, mxS = 0; mnH.insert(min(seg[0].X, seg[0].Y)); mnS += min(seg[0].X, seg[0].Y); mxH.insert(max(seg[0].X, seg[0].Y)); mxS += max(seg[0].X, seg[0].Y); pre[1] = mxS - mnS; for (ll i = 2; i <= sz(seg); i ++){ if (seg[i - 1].X <= *mxH.begin()){ mnH.insert(seg[i - 1].X); mnS += seg[i - 1].X; } else{ auto itr = mxH.begin(); mxS -= *itr; mnS += *itr; mnH.insert(*itr); mxH.erase(itr); mxS += seg[i - 1].X; mxH.insert(seg[i - 1].X); } if (seg[i - 1].Y <= *mxH.begin()){ mnH.insert(seg[i - 1].Y); mnS += seg[i - 1].Y; } else{ auto itr = mxH.begin(); mxS -= *itr; mnS += *itr; mnH.insert(*itr); mxH.erase(itr); mxS += seg[i - 1].Y; mxH.insert(seg[i - 1].Y); } if (sz(mnH) < sz(mxH)){ auto itr = mxH.begin(); mxS -= *itr; mnS += *itr; mnH.insert(*itr); mxH.erase(itr); } if (sz(mxH) < sz(mnH)){ auto itr = mnH.rbegin(); mnS -= *itr; mxS += *itr; mxH.insert(*itr); mnH.erase(mnH.find(*itr)); } pre[i] = mxS - mnS; } mnH.clear(); mxH.clear(); mnS = mxS = 0; mnH.insert(min(seg.back().X, seg.back().Y)); mnS += min(seg.back().X, seg.back().Y); mxH.insert(max(seg.back().X, seg.back().Y)); mxS += max(seg.back().X, seg.back().Y); suf[sz(seg)] = mxS - mnS; for (ll i = sz(seg) - 1; i >= 1; i --){ if (seg[i - 1].X <= *mxH.begin()){ mnH.insert(seg[i - 1].X); mnS += seg[i - 1].X; } else{ auto itr = mxH.begin(); mxS -= *itr; mnS += *itr; mnH.insert(*itr); mxH.erase(itr); mxS += seg[i - 1].X; mxH.insert(seg[i - 1].X); } if (seg[i - 1].Y <= *mxH.begin()){ mnH.insert(seg[i - 1].Y); mnS += seg[i - 1].Y; } else{ auto itr = mxH.begin(); mxS -= *itr; mnS += *itr; mnH.insert(*itr); mxH.erase(itr); mxS += seg[i - 1].Y; mxH.insert(seg[i - 1].Y); } if (sz(mnH) < sz(mxH)){ auto itr = mxH.begin(); mxS -= *itr; mnS += *itr; mnH.insert(*itr); mxH.erase(itr); } if (sz(mxH) < sz(mnH)){ auto itr = mnH.rbegin(); mnS -= *itr; mxS += *itr; mxH.insert(*itr); mnH.erase(mnH.find(*itr)); } suf[i] = mxS - mnS; } ll ANS = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000; for (int i = 0; i <= sz(seg); i ++) ANS = min(ANS, pre[i] + suf[i + 1] + EXT + sz(seg)); cout << ANS; return 0; }
#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...