제출 #490575

#제출 시각아이디문제언어결과실행 시간메모리
490575DeadlyCriticPalembang Bridges (APIO15_bridge)C++17
8 / 100
72 ms25736 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("O2,unroll-loops") // #pragma GCC optimize("no-stack-protector,fast-math") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie(); #define fr first #define sc second #define all(v) v.begin(), v.end() #define uni(v) sort(all(v)), v.erase(unique(all(v)), v.end()) // #define c0 (v << 1) // #define c1 (c0 | 1) // #define md ((l+r)>>1) using namespace std; typedef long long ll; const int maxN = 1e5+7; int k, n, sz; ll fix; vector<pair<int, int>> ed; vector<int> df; map<int, int> mp; int demp[maxN]; pair<int, int> pr[maxN]; vector<int> st[maxN], en[maxN]; ll dis(pair<int, int> a, ll p){ return abs(a.fr-p)+abs(a.sc-p)+1; } signed main(){IOS cin >> k >> n; for(int i = 0; i < n; i++){ char t1, t2; int x1, x2; cin >> t1 >> x1 >> t2 >> x2; if(t1 == t2){ fix += abs(x2-x1); } else{ ed.push_back({min(x1, x2), max(x1, x2)}); df.push_back(x1); df.push_back(x2); } } n = ed.size(); uni(df); sz = df.size(); for(int i = 0; i < sz; i++)mp[df[i]] = i, demp[i] = df[i]; for(int i = 0; i < n; i++){ ed[i].fr = mp[ed[i].fr]; ed[i].sc = mp[ed[i].sc]; pr[i] = {ed[i].fr, ed[i].sc}; st[ed[i].fr].push_back(i); en[ed[i].sc].push_back(i); } assert(k == 1); if(k == 1){ int po = 0; ll now = 0; int l = en[po].size(), r = n-st[po].size(); for(int i = 0; i < n; i++){ ll x = dis({demp[ed[i].fr], demp[ed[i].sc]}, demp[po]); now += x; } ll ans = now; while(po+1 < sz){ ll delt = demp[po+1]-demp[po]; now += (l*2-r*2)*delt; ans = min(ans, now); po++; l += en[po].size(); r -= st[po].size(); } cout << fix+ans << '\n'; return 0; } } /* 1 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */
#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...