Submission #244408

#TimeUsernameProblemLanguageResultExecution timeMemory
244408WhaleVomitPalembang Bridges (APIO15_bridge)C++14
22 / 100
244 ms20960 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back #define mp make_pair #define all(v) v.begin(), v.end() #define sz(v) (int)v.size() #define MOO(i, a, b) for(int i=a; i<b; i++) #define M00(i, a) for(int i=0; i<a; i++) #define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--) #define M00d(i,a) for(int i = (a)-1; i>=0; i--) #define FAST ios::sync_with_stdio(0); cin.tie(0); #define finish(x) return cout << x << '\n', 0; #define dbg(x) cerr << ">>> " << #x << " = " << x << "\n"; #define _ << " _ " << typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int,int> pi; typedef pair<ld,ld> pd; typedef complex<ld> cd; const int MAX_N = 100100; int k, n; vector<pi> arr; map<int,int> startsAt; map<int,int> endsAt; vi points; ll getMinDis1() { ll cur = 0; ll numBefore = 0; ll numAfter = 0; for(pi p: arr) if(p.f > points[0]) { numAfter++; cur += p.f - points[0]; } ll ans = cur; MOO(i, 1, sz(points)) { cur -= numAfter*(points[i] - points[i-1]); numAfter -= startsAt[points[i]]; numBefore += endsAt[points[i-1]]; cur += numBefore*(points[i] - points[i-1]); ans = min(ans, cur); } return ans; } vector<ll> getVals(vector<pi>& v) { ll val = 0; ll startAfter = 0; ll endBefore = 0; multiset<pi> stuff; // (x,0) = start at x, (x,1) = end at x stuff.insert(mp(v[0].f ,0)); stuff.insert(mp(v[0].s, 1)); vector<ll> res; res.pb(0); res.pb(val); auto it = stuff.begin(); MOO(i, 1, sz(v)) { stuff.insert(mp(v[i].f, 0)); if(v[i].f > (*it).f) { val += v[i].f - (*it).f; startAfter++; } stuff.insert(mp(v[i].s, 1)); if(v[i].s < (*it).f) { val += (*it).f - v[i].s; endBefore++; } while(startAfter > endBefore) { if(next(it) == stuff.end()) break; int curx = (*it).f; int nextx = (*(next(it))).f; val -= startAfter*(nextx - curx); if((*it).s == 1) endBefore++; it++; if((*it).s == 0) startAfter--; val += endBefore*(nextx - curx); } while(startAfter < endBefore) { if(it == stuff.begin()) break; int curx = (*it).f; int nextx = (*(prev(it))).f; val -= endBefore*(curx - nextx); if((*it).s == 0) startAfter++; it--; if((*it).s == 1) endBefore--; val += startAfter*(curx - nextx); } res.pb(val); } return res; } ll getMinDis2() { vector<pair<int, pi>> tmp; M00(i, sz(arr)) { tmp.pb(mp(arr[i].f + arr[i].s, arr[i])); } sort(all(tmp)); vector<pi> sorted; M00(i, sz(tmp)) sorted.pb(tmp[i].s); vector<ll> v1 = getVals(sorted); reverse(all(sorted)); vector<ll> v2 = getVals(sorted); reverse(all(v2)); ll ans = 1e18; M00(i, sz(v1)) { ans = min(ans, v1[i]+v2[sz(v2)-1-i]); } return ans; } int main() { FAST cin >> k >> n; int cnt = 0; ll ans = 0; M00(i, n) { string s1, s2; int i1, i2; cin >> s1 >> i1 >> s2 >> i2; if(i1 > i2) swap(i1, i2); if(s1 == s2) { ans += (i2-i1); } else { cnt++; ans += (i2-i1); arr.pb(mp(i1,i2)); startsAt[i1]++; endsAt[i2]++; points.pb(i1); points.pb(i2); } } sort(all(points)); points.erase(unique(all(points)), points.end()); if(k == 1) { ans += getMinDis1()*2LL + cnt; } else { ans += getMinDis2()*2LL + cnt; } finish(ans); }
#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...