Submission #1093283

#TimeUsernameProblemLanguageResultExecution timeMemory
1093283giaminh2211Palembang Bridges (APIO15_bridge)C++14
22 / 100
32 ms1608 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second using namespace std; using namespace __gnu_pbds; using ll=long long; using pii=pair<int, int>; struct GetMedian{ multiset<ll> fi; multiset<ll> se; ll fsum=0, ssum=0; void add(ll x){ se.insert(x); ssum+=x; while(fi.size() && fi.size() > se.size()){ ll val=*fi.rbegin(); fsum-=val; fi.erase(fi.find(val)); se.insert(val); ssum+=val; } while(se.size() && se.size() > fi.size()){ ll val=*se.begin(); ssum-=val; se.erase(se.begin()); fi.insert(val); fsum+=val; } } ll get(){ ll med=*fi.rbegin(); ll val=(med * fi.size() - fsum) + (ssum - med * se.size()); return val; } void clear(){ fi.clear(); se.clear(); fsum=ssum=0; } }; int k, n; const int N=1e5+13; int a[N]; ll res; char c1, c2; int x, y; namespace sub1{ vector<int> v; void solve(){ for(int i=1; i<=n; i++){ cin >> c1 >> x >> c2 >> y; if(c1==c2){ res+=abs(x-y); } else{ v.push_back(x); v.push_back(y); ++res; } } sort(begin(v), end(v)); for(int c: v){ res+=abs(c-v[v.size()/2]); } cout << res; } } vector<pair<int, int>> v; ll l[N]; ll r[N]; void solve(){ cin >> k >> n; if(k==1){ sub1::solve(); exit(0); } v.push_back({0, 0}); for(int i=1; i<=n; i++){ cin >> c1 >> x >> c2 >> y; if(c1==c2){ res+=abs(x-y); } else{ if(x > y) swap(x, y); v.push_back(make_pair(x, y)); ++res; } } if(v.empty()){ cout << res; return; } sort(begin(v)+1, end(v), [&](pii x, pii y){ return x.fi + x.se < y.fi + y.se; }); n=v.size()-1; GetMedian sus; for(int i=1; i<=n; i++){ sus.add(v[i].fi); sus.add(v[i].se); l[i]=sus.get(); } sus.clear(); for(int i=n; i>=1; i--){ sus.add(v[i].fi); sus.add(v[i].se); r[i]=sus.get(); } ll ans=l[n]; for(int i=1; i<n; i++){ ans=min(ans, l[i]+r[i+1]); } cout << res+ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); solve(); }
#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...