Submission #499131

#	Time	Username	Problem	Language	Result	Execution time	Memory
499131		Stickfish	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	591 ms	37104 KiB

bridge

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;
using ll = long long;

const ll INF = 1.77013e15;

mt19937 rng(time(0));

struct abssm {
    abssm() {
        root = new node();
        root->prior = rng();
        root->x = -INF;
        root->slope = root->y = 0;
    }
    
    ll find_opty() {
        node* nd = find_nonneg(root);
        return nd->y;
    }

    void addabs(ll x) {
        auto [l, r] = split_x(root, x);
        node* nd = find_first(r);
        node* pv = find_last(l);
        if (!nd || nd->x != x) {
            node* nd0 = new node();
            nd0->prior = rng();
            nd0->x = x;
            nd0->y = pv->y + (x - pv->x) * pv->slope;
            nd0->slope = pv->slope;
            r = merge(nd0, r);
        }
        r->lazy_slope += 1;
        r->lazy_y += r->x - x;
        l->lazy_slope += -1;
        l->lazy_y += x - l->x;
        root = merge(l, r);
    }

    void output() {
        output(root);
    }

 private:
    struct node {
        node* l = nullptr;
        node* r = nullptr;
        ll prior;
        ll x;
        ll y;
        ll slope;
        ll lazy_slope = 0;
        ll lazy_y = 0;
    };

    void output(node* nd) {
        if (!nd)
            return;
        push(nd);
        output(nd->l);
        cout << "(" << nd->x << ' ' << nd->y << ' ' << nd->slope << ") ";
        output(nd->r);
    }

    node* root;

    void push(node* nd) {
        if (nd->l) {
            nd->l->lazy_slope += nd->lazy_slope;
            nd->l->lazy_y += (nd->l->x - nd->x) * nd->lazy_slope + nd->lazy_y;
        }
        if (nd->r) {
            nd->r->lazy_slope += nd->lazy_slope;
            nd->r->lazy_y += (nd->r->x - nd->x) * nd->lazy_slope + nd->lazy_y;
        }
        nd->y += nd->lazy_y;
        nd->lazy_y = 0;
        nd->slope += nd->lazy_slope;
        nd->lazy_slope = 0;
    }

    pair<node*, node*> split_x(node* nd, ll x) {
        if (!nd)
            return {nullptr, nullptr};
        push(nd);
        if (x <= nd->x) {
            auto [l, r] = split_x(nd->l, x);
            nd->l = r;
            return {l, nd};
        } else {
            auto [l, r] = split_x(nd->r, x);
            nd->r = l;
            return {nd, r};
        }
    }

    node* merge(node* l, node* r) {
        if (!l && !r)
            return nullptr;
        if (!l) {
            push(r);
            return r;
        }
        if (!r) {
            push(l);
            return l;
        }
        push(l);
        push(r);
        if (l->prior > r->prior) {
            node* lr = merge(l->r, r);
            l->r = lr;
            return l;
        } else {
            node* rl = merge(l, r->l);
            r->l = rl;
            return r;
        }
    }

    node* find_nonneg(node* nd) {
        if (!nd)
            return nullptr;
        push(nd);
        if (nd->slope < 0)
            return find_nonneg(nd->r);
        node* l = find_nonneg(nd->l);
        if (l)
            return l;
        if (nd->slope >= 0)
            return nd;
        return nullptr;
    }

    node* find_first(node* nd) {
        if (!nd)
            return nullptr;
        push(nd);
        if (!nd->l)
            return nd;
        return find_first(nd->l);
    }

    node* find_last(node* nd) {
        if (!nd)
            return nullptr;
        push(nd);
        if (!nd->r)
            return nd;
        return find_last(nd->r);
    }
};

const ll MAXN = 100003;
pair<ll, ll> sg[MAXN];
ll pref_ans[MAXN];
ll suf_ans[MAXN];

signed main() {
    ll k, n = 0;
    ll n0;
    cin >> k >> n0;
    ll addans = 0;
    for (ll i = 0; i < n0; ++i) {
        char c1, c2;
        ll d1, d2;
        cin >> c1 >> d1 >> c2 >> d2;
        if (d1 > d2)
            swap(d1, d2);
        d1 *= 2;
        d2 *= 2;
        if (c1 == c2) {
            addans += d2 - d1;
        } else {
            sg[n] = {(d1 + d2) / 2, (d2 - d1) / 2};
            ++n;
        }
    }
    sort(sg, sg + n);
    //for (ll i = 0; i < n; ++i)
        //cout << "(" << sg[i].first - sg[i].second << ' ' << sg[i].first + sg[i].second << ") ";
    //cout << endl;
    abssm t;
    for (ll i = 0; i < n; ++i) {
        t.addabs(sg[i].first - sg[i].second);
        t.addabs(sg[i].first + sg[i].second);
        //t.output();
        //cout << endl;
        pref_ans[i] = t.find_opty();
    }
    abssm t0;
    for (ll i = n - 1; i >= 0; --i) {
        t0.addabs(sg[i].first - sg[i].second);
        t0.addabs(sg[i].first + sg[i].second);
        suf_ans[i] = t0.find_opty();
    }
    //for (ll i = 0; i < n; ++i) {
        //cout << pref_ans[i] << ' ' << suf_ans[i] << endl;
    //}
    if (k == 1) {
        cout << (pref_ans[n - 1] + addans) / 2 + n << endl;
    } else {
        ll ans = suf_ans[0];
        for (ll i = 0; i < n; ++i) {
            ans = min(ans, pref_ans[i] + suf_ans[i + 1]);
        }
        cout << (ans + addans) / 2 + n << endl;
    }
}

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