Submission #1110872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110872		vladilius	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	3 ms	1360 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();

struct DS{
    struct node{
        int s1; ll s2;
        node *l, *r;
        node(){
            s1 = s2 = 0;
            l = r = 0;
        }
        node(int x, ll y){
            s1 = x; s2 = y;
            l = r = 0;
        }
        node(node *ls, node *rs){
            l = ls; r = rs;
            s1 = s2 = 0;
            if (l){
                s1 += l -> s1;
                s2 += l -> s2;
            }
            if (r){
                s1 += r -> s1;
                s2 += r -> s2;
            }
        }
    };
    node *rt;
    int n;
    void init(){
        rt = new node();
        n = 1e9;
    }
    node* upd(node *v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            return new node(v -> s1 + 1, v -> s2 + x);
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            if (!(v -> l)) v -> l = new node();
            return new node(upd(v -> l, tl, tm, p, x), v -> r);
        }
        else {
            if (!(v -> r)) v -> r = new node();
            return new node(v -> l, upd(v -> r, tm + 1, tr, p, x));
        }
    }
    void upd(int p, int x){
        rt = upd(rt, 1, n, p, x);
    }
    pil get(node *v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return {0, 0};
        if (l <= tl && tr <= r){
            return {v -> s1, v -> s2};
        }
        int tm = (tl + tr) / 2;
        pil p1 = {0, 0}, p2 = {0, 0};
        if (v -> l) p1 = get(v -> l, tl, tm, l, r);
        if (v -> r) p2 = get(v -> r, tm + 1, tr, l, r);
        return {p1.ff + p2.ff, p1.ss + p2.ss};
    }
    pair<int, ll> get(int l, int r){
        return get(rt, 1, n, l, r);
    }
    
    vector<int> all;
    set<int> s1, s2;
    void add(int x){
        s1.insert(x);
        if (s1.size() > s2.size()){
            int y = *prev(s1.end());
            s1.erase(s1.find(y));
            s2.insert(y);
        }
        if (!s1.empty() && !s2.empty()){
            int a = *prev(s1.end()), b = *s2.begin();
            if (a > b){
                s1.erase(s1.find(a));
                s2.erase(s2.find(b));
                s1.insert(b);
                s2.insert(a);
            }
        }
        upd(x, x);
    }
    ll get(){
        if (s2.empty()) return 0;
        int x = *s2.begin();
        ll out = 0;
        for (int i: all){
            out += abs(i - x);
        }
        
        pil p1 = get(1, x), p2 = get(x + 1, n);
        return (1LL * x * p1.ff - p1.ss) + (p2.ss - 1LL * x * p2.ff);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int k, n; cin>>k>>n;
    vector<pii> all;
    ll out = 0;
    while (n--){
        char t1, t2; int x1, y1; cin>>t1>>x1>>t2>>y1;
        if (t1 == t2){
            out += abs(x1 - y1);
            continue;
        }
        if (x1 > y1) swap(x1, y1);
        all.pb({x1, y1});
    }
    
    n = (int) all.size();
    vector<int> imp;
    for (int i = 0; i < n; i++){
        imp.pb(all[i].ff); imp.pb(all[i].ss);
    }

    ll mn = inf;
    if (k == 1){
        vector<int> f;
        for (auto [x, y]: all){
            f.pb(x); f.pb(y);
        }
        sort(f.begin(), f.end());
        int x = f[(int) (f.size() - 1) / 2];
        ll sum = 0;
        for (int i: f){
            sum += abs(i - x);
        }
        mn = sum + n;
    }
    else {
        ll S = 0;
        for (auto [x, y]: all){
            S += (y - x);
        }
        
        int h = (int) imp.size();
        sort(imp.begin(), imp.end());
        vector<ll> out1(h), out2(h), h1(h), h2(h);
        vector<pii> p1(h), p2(h);
        
        auto cmp = [&](pii x, pii y){
            return x.ss < y.ss;
        };
        
        sort(all.begin(), all.end(), cmp);
        int j = 0;
        DS T1; T1.init();
        for (int i = 0; i < h; i++){
            p2[i] = (!i) ? make_pair(0, 0) : p2[i - 1];
            h2[i] = (!i) ? 0 : h2[i - 1];
            while (j < n && all[j].ss < imp[i]){
                T1.add(all[j].ff);
                T1.add(all[j].ss);
                p2[i].ff++;
                p2[i].ss += (all[j].ff + all[j].ss);
                h2[i] += (all[j].ss - all[j].ff);
                j++;
            }
            out1[i] = T1.get();
        }

        sort(all.begin(), all.end());
        j = n - 1;
        DS T2; T2.init();
        for (int i = h - 1; i >= 0; i--){
            p1[i] = (i == (h - 1)) ? make_pair(0, 0) : p1[i + 1];
            h1[i] = (i == (h - 1)) ? 0 : h1[i + 1];
            while (j >= 0 && all[j].ff > imp[i]){
                T2.add(all[j].ff);
                T2.add(all[j].ss);
                p1[i].ff++;
                p1[i].ss += (all[j].ff + all[j].ss);
                h1[i] += (all[j].ss - all[j].ff);
                j--;
            }
            out2[i] = T2.get();
        }
        
        for (int j = 0; j < h; j++){
            int i = imp[j];
            ll sum = S - h1[j] - h2[j];
            ll s1 = out1[j] + p1[j].ss - 2LL * i * p1[j].ff;
            ll s2 = out2[j] + 2LL * i * p2[j].ff - p2[j].ss;
            
            mn = min(mn, sum + s1 + n);
            mn = min(mn, sum + s2 + n);
        }
    }
    if (mn == inf) mn = 0;
    cout<<out + mn<<"\n";
}

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