Submission #1267410

#TimeUsernameProblemLanguageResultExecution timeMemory
1267410ChuanChenPalembang Bridges (APIO15_bridge)C++20
22 / 100
86 ms10516 KiB
#include<bits/stdc++.h> #define debug(v) //cerr << #v << ": " << v << '\n'; using namespace std; typedef pair<int, int> pii; typedef long long ll; int k, n; ll ans; vector<pii> inter; bool cmp(pii a, pii b){ return a.first+a.second < b.first+b.second; } struct two_set{ multiset<int> s1, s2; //s1-> smaller than mid //s2 -> greater than mid; //s1.size() >= s2.size(); ll sum1, sum2; ll median(){ if(s1.empty()){ // cerr << "empty set\n"; return 0; } return *s1.rbegin(); } void add(int v){ if(s1.empty()){ s1.insert(v); sum1 += v; return; } if(s1.size() == s2.size()){ if(v <= *s2.begin()){ sum1 += v; s1.insert(v); } else{ sum2 += v; s2.insert(v); sum1 += *s2.begin(); s1.insert( *s2.begin() ); sum2 -= *s2.begin(); s2.erase(s2.begin()); } } else{ sum1 += v; s1.insert(v); sum2 += *(--s1.end()); s2.insert( *(--s1.end()) ); sum1 -= *(--s1.end()); s1.erase( --s1.end() ); } } void remove(int v){ if(s1.size() == s2.size()){ if(v < *s2.begin()){ sum1 -= v; s1.erase(s1.find(v)); sum1 += *s2.begin(); s1.insert(*s2.begin()); sum2 -= *s2.begin(); s2.erase(s2.begin()); } else{ sum2 -= v; s2.erase(s2.find(v)); } } else{ if(v <= *s1.rbegin()){ sum1 -= v; s1.erase(s1.find(v)); } else{ sum2 -= v; s2.erase(s2.find(v)); sum2 += *(--s1.end()) ; s2.insert( *(--s1.end()) ); sum1 -= *(--s1.end()) ; s1.erase( --s1.end() ); } } } ll dist(){ return s1.size()*median()-sum1 + sum2 - s2.size()*median(); } }; two_set esq, dir; signed main(){ cin.tie(0)->sync_with_stdio(0); int k, n; cin >> k >> n; for(int i = 1; i <= n; i++){ char za, zb; int a, b; cin >> za >> a >> zb >> b; if(a>b) swap(a, b); if(za==zb){ ans += b-a; } else{ ans++; inter.push_back({a, b}); } } debug(ans) sort(inter.begin(), inter.end(), cmp); for(auto[L, R] : inter){ dir.add(L); dir.add(R); debug(L); debug(R); debug(dir.median()); debug(dir.dist()); } debug(dir.median()); if(k == 1){ cout << ans+dir.dist() << '\n'; return 0; } ll best = 1e18; for(auto[L, R] : inter){ dir.remove(L); dir.remove(R); esq.add(L); esq.add(R); debug(dir.median()); debug(dir.dist()); debug(esq.median()); debug(esq.dist()); debug(' '); best = min(best, dir.dist()+esq.dist()); } debug(best) cout << ans+best << '\n'; }
#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...