제출 #890760

#제출 시각아이디문제언어결과실행 시간메모리
890760dwuyPalembang Bridges (APIO15_bridge)C++14
100 / 100
696 ms10092 KiB
/// dwuy: _,\,,,_\,__,\,,_ #include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout) #define fi first #define se second #define endl "\n" #define len(s) int32_t(s.length()) #define MASK(k)(1LL<<(k)) #define TASK "" #define int long long using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD = 1e9 + 7; const int INF = 1e9; const int MX = 100005; int n, K, sum; int b[MX]; int c[MX]; pii a[MX]; pii Q[MX]; vector<int> id; void nhap(){ cin >> K >> n; int t = 0; for(int i=1; i<=n; i++){ int l, r; char t1, t2; cin >> t1 >> l >> t2 >> r; if(l > r) swap(l, r); sum += r-l; if(t1 != t2) a[++t] = {l, r}; } n = t; sum += n; if(n==0) cout << sum, exit(0); } int lower_bound_B(int x){ int res = 0; for(int lo=1, hi=n; lo<=hi;){ int mid = (lo+hi)>>1; if(b[mid] - b[mid-1] <= x) res = mid, lo = mid + 1; else hi = mid - 1; } return res; } void subK1(){ int l=0, r=1; int res = OO; for(int x: id){ while(l<n && b[l+1] - b[l] <= x) l++; while(r<=n && c[r] - c[r+1] <= x) r++; res = min(res, (x*l - b[l] + c[r] - x*(n-r+1))*2); } cout << res + sum; } int calc(int mid){ int res = OO, cur = 0; int qID = 0; cur = id[mid]*(lower_bound_B(id[mid])) - b[lower_bound_B(id[mid])]; for(int i=1; i<=n; i++) if(a[i].fi>id[mid]){ Q[++qID] = {a[i].se + a[i].fi - id[mid], a[i].se}; cur += a[i].fi - id[mid]; } sort(Q+1, Q+1+qID); int j = n+1; int Extra = 0; priority_queue<int, vector<int>, greater<int>> extraQ; for(int i=(int)id.size()-1; i>mid; i--){ while(qID && Q[qID].fi - id[i] >= 0){ cur = cur - (Q[qID].fi - Q[qID].se) + id[i] - Q[qID].se + Extra; extraQ.push(id[i] - Q[qID].se + Extra); qID--; } while(extraQ.size() && extraQ.top() <= Extra){ cur -= extraQ.top(); extraQ.pop(); } while(c[j-1] - c[j] >= id[i]) j--; res = min(res, cur - Extra*(int)extraQ.size() + c[j] - id[i]*(n-j+1) ); Extra += id[i] - id[i-1]; } return res*2; } void subK2(){ int res = OO; for(int lo=0, hi=(int)id.size()/2; lo<=hi;){ int mid = (lo+hi)>>1; if(lo+1>=hi){ res = min({res, calc(lo), calc(hi)}); break; } int cost1 = calc(mid-1); int cost2 = calc(mid+1); if(cost1 < cost2) res = min(res, cost1), hi = mid; if(cost1 > cost2) res = min(res, cost2), lo = mid; if(cost1 == cost2) res = min(res, calc(mid)), lo=hi+1; } for(int lo=(int)id.size()/4 + 1, hi=(int)id.size()/2; lo<=hi;){ int mid = (lo+hi)>>1; if(lo+1>=hi){ res = min({res, calc(lo), calc(hi)}); break; } int cost1 = calc(mid-1); int cost2 = calc(mid+1); if(cost1 < cost2) res = min(res, cost1), hi = mid; if(cost1 > cost2) res = min(res, cost2), lo = mid; if(cost1 == cost2) res = min(res, calc(mid)), lo=hi+1; } // for(int lo=(int)id.size()/2, hi=(int)id.size()/4*3; lo<=hi;){ // int mid = (lo+hi)>>1; // if(lo+1>=hi){ // res = min({res, calc(lo), calc(hi)}); // break; // } // int cost1 = calc(mid-1); // int cost2 = calc(mid+1); // if(cost1 < cost2) res = min(res, cost1), hi = mid; // if(cost1 > cost2) res = min(res, cost2), lo = mid; // if(cost1 == cost2) res = min(res, calc(mid)), lo=hi+1; // } cout << res + sum << endl; } void solve(){ id.resize(n+n); for(int i=1; i<=n; i++){ id[i-1] = a[i].fi; id[i+n-1] = a[i].se; b[i] = a[i].se; c[i] = a[i].fi; } sort(id.begin(), id.end()); id.erase(unique(id.begin(), id.end()), id.end()); sort(a+1, a+1+n); sort(b+1, b+1+n); sort(c+1, c+1+n); for(int i=1; i<=n; i++) b[i] += b[i-1]; for(int i=n; i>=1; i--) c[i] += c[i+1]; if(K==1){ subK1(); return; } if(K==2){ subK2(); return; } } int32_t main(){ fastIO; //file(TASK); nhap(); solve(); return 0; } /** 2 6 A 1 B 3 A 2 B 4 A 3 B 5 A 4 B 6 A 5 B 7 A 6 B 8 **/
#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...