Submission #732485

#	Time	Username	Problem	Language	Result	Execution time	Memory
732485		hafo	Palembang Bridges (APIO15_bridge)	C++14	78 / 100	329 ms	14416 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e9 + 69;

int k, n;
ll fa[maxn], fb[maxn], ans = 0;
vector<int> a, b, point;

ll calc(int i) {
    int id = upper_bound(all(a), i) - a.begin();
    ll res = 1LL * i * id - fa[id] + fa[(int) a.size()] - fa[id] - 1LL * i * ((int) a.size() - id);
    id = upper_bound(all(b), i) - b.begin();
    res = res + 1LL * i * id - fb[id] + fb[(int) b.size()] - fb[id] - 1LL * i * ((int) b.size() - id);
    return res;
}

void sub1() {
    for(auto i:a) point.pb(i);
    for(auto i:b) point.pb(i);
    sort(all(point));
    sort(all(a));
    sort(all(b));
    fa[0] = fb[0] = 0;
    for(int i = 1; i <= (int) a.size(); i++) fa[i] = fa[i - 1] + a[i - 1];
    for(int i = 1; i <= (int) b.size(); i++) fb[i] = fb[i - 1] + b[i - 1];

    ll mn = oo;
    for(auto i:point) mini(mn, calc(i));
    ans += (int) a.size() + mn;
}

struct sliding_median {
    multiset<int> low, high;
    ll lsum, rsum;

    void init() {
        multiset<int> tmp;
        low = tmp;
        high = tmp;
        lsum = rsum = 0;
    }

    void fix() {
        if(low.size() < high.size()) {
            int val = *high.begin();
            lsum += val;
            rsum -= val;
            low.insert(val);
            high.erase(high.find(val));
        } else if((int) low.size() > (int) high.size() + 1) {
            int val = *low.rbegin();
            lsum -= val;
            rsum += val;
            low.erase(low.find(val));
            high.insert(val);
        }
    }

    void update(int x) {
        int med = (low.empty() ? oo:*low.rbegin());
        if(x < med){
            lsum += x;
            low.insert(x);
        }
        else {
            rsum += x;
            high.insert(x);
        }
        fix();
    }

    void Remove(int x) {
        if(low.find(x) != low.end()) {
            lsum -= x;
            low.erase(low.find(x));
        }
        else {
            rsum -= x;
            high.erase(high.find(x));
        }
        fix();
    }
} s;

bool cmp(pa a, pa b) {
    return a.fi + a.se < b.fi + b.se;
}

void sub2(){
    int m = (int) a.size();
    vector<pa> val;
    for(int i = 0; i < m; i++) {
        val.pb({a[i], b[i]});
    }
    sort(all(val), cmp);
    s.init();
    for(int i = 1; i <= m; i++) {
        s.update(val[i - 1].fi);
        s.update(val[i - 1].se);
        fa[i] = s.rsum - s.lsum;
    }

    s.init();
    ll mn = fa[m];
    for(int i = m; i >= 1; i--) {
        s.update(val[i - 1].fi);
        s.update(val[i - 1].se);
        mini(mn, fa[i - 1] + s.rsum - s.lsum);
    }
    ans += (mn + m);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>k>>n;
    ans = 0;
    for(int i = 0; i < n; i++){
        char ch1, ch2;
        int x, y;
        cin>>ch1>>x>>ch2>>y;
        if(ch1 == ch2) ans += abs(x - y);
        else {
            if(ch1 == 'A') a.pb(x);
            else b.pb(x);
            if(ch2 == 'A') a.pb(y);
            else b.pb(y);
        }
    }


    if(k == 1) {
        sub1();
    } else {
        sub2();
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37