| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 673565 | Cookie | Palembang Bridges (APIO15_bridge) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#include<fstream>
ifstream fin("cowpatibility.in");
ofstream fout("cowpatibility.out");
#define pii pair<int, int>
#define pll pair<ll, ll>
#define int long long
const ll mod = 1e9 + 7, mod2 = 1e9 + 9;
const int mxn = 2e5;
int k, n;
ll ans = 0;
struct BIT{
ll bit[mxn + 1];
void init(){
for(int i = 0; i <= mxn; i++)bit[i] = 0;
}
void upd(int p, ll v){
p--;
while(p <= mxn){
bit[p] += v;
p |= (p + 1);
}
}
ll get(int p){
ll ans = 0;
while(p > 0){
ans += bit[p - 1];
p &= (p - 1);
}
return(ans);
}
int kth(int x){
int p = 0;
for(int i = 1 << 17; i; i >>= 1){
if(p + i <= mxn && bit[p + i - 1] < x){
p += i; x -= bit[p - 1];
}
}
return(p);
}
};
BIT cnt, sm;
vt<ll>comp;
ll p[mxn + 1];
vt<pll>v;
void solve1(){
vt<ll>points;
for(auto [aa, bb]: v){
points.pb(aa); points.pb(bb);
}
sort(points.begin(), points.end());
ll med = points[points.size() / 2];
for(int i = 0; i < points.size(); i++){
ans += abs(med - points[i]);
}
cout << ans;
}
bool cmp(pll a, pll b){
return((a.fi + a.se) < (b.fi + b.se));
}
void add(ll x){
//cout << comp[x - 1] << " ";
cnt.upd(x, 1); sm.upd(x, comp[x - 1]);
}
ll gett(int x){
ll ans = sm.get(mxn) - sm.get(x) - (cnt.get(mxn) - cnt.get(x)) * comp[x - 1];
//cout << ans << " ";
ans += cnt.get(x) * comp[x - 1] - sm.get(x);
//cout << ans << " ";
return(ans);
}
int med(int kk){
int len = (kk + 1) / 2;
int pos = cnt.kth(len);
return(pos + 1);
}
void solve2(){
sort(v.begin(), v.end(), cmp);
for(int i = 0; i < v.size(); i++){
comp.pb(v[i].fi); comp.pb(v[i].se);
}
sort(comp.begin(), comp.end());
for(int i = 0; i < v.size(); i++){
v[i].fi = lower_bound(comp.begin(), comp.end(), v[i].fi) - comp.begin() + 1;
v[i].se = lower_bound(comp.begin(), comp.end(), v[i].se) - comp.begin() + 1;
}
for(int i = 0; i < v.size(); i++){
add(v[i].fi); add(v[i].se);
p[i] = gett(med((i + 1) * 2));
}
cnt.init(); sm.init();
ll res = p[v.size() - 1];
for(int i = v.size() - 1; i >= 1; i--){
add(v[i].fi); add(v[i].se);
res = min(res, gett(med((v.size() - i) * 2)) + p[i - 1]);
}
cout << ans + res;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> k >> n;
forr(i, 0, n){
char a, b; ll aa, bb;
cin >> a >> aa >> b >> bb;
if(a == b)ans += abs(aa - bb);
else v.pb({aa, bb});
}
ans += v.size();
if(k == 1)solve1();
else solve2();
return 0;
}