Submission #1290572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290572		ProtonDecay314	Nile (IOI24_nile)	C++20	100 / 100	146 ms	41144 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;

#define pb push_back
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()

struct ParTree {
    ParTree* lt, *rt;
    ll l, r;
    pll v;

    ParTree(ll a_l, ll a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v({INF(ll), INF(ll)}) {}

    inline pll combine(pll lv, pll rv) {
        return {min(lv.first, rv.first), min(lv.second, rv.second)};
    }

    void build(const vll& a) {
        if(l == r) {
            if(l & 0b1ll) {
                // odd, put in second
                v.second = a[l];
            } else {
                v.first = a[l];
            }
            return;
        }

        ll m = (l + r) >> 1ll;

        lt = new ParTree(l, m);
        rt = new ParTree(m + 1ll, r);

        lt->build(a);
        rt->build(a);

        v = combine(lt->v, rt->v);
    }

    pll qry(ll ql, ll qr) {
        if(ql > r || qr < l) return {INF(ll), INF(ll)};

        if(ql == l && qr == r) return v;

        ll m = (l + r) >> 1ll;

        return combine(lt->qry(ql, min(qr, m)), rt->qry(max(ql, m + 1ll), qr));
    }
};

struct MinTree {
    MinTree *lt, *rt;
    ll l, r;
    ll v;

    MinTree(ll a_l, ll a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(INF(ll)) {}

    inline ll combine(ll lv, ll rv) {
        return min(lv, rv);
    }

    void build(const vll& a) {
        if(l == r) {
            v = a[l];
            return;
        }

        ll m = (l + r) >> 1ll;

        lt = new MinTree(l, m);
        rt = new MinTree(m + 1ll, r);

        lt->build(a);
        rt->build(a);

        v = combine(lt->v, rt->v);
    }

    void upd(ll i, ll nv) {
        if(r < i || l > i) return;

        if(l == r) {
            v = nv;
            return;
        }

        ll m = (l + r) >> 1ll;

        if(i <= m) lt->upd(i, nv);
        else rt->upd(i, nv);

        v = combine(lt->v, rt->v);
    }

    ll qry(ll ql, ll qr) {
        if(ql > r || qr < l) return INF(ll);

        if(ql == l && qr == r) return v;
        ll m = (l + r) >> 1ll;

        return combine(lt->qry(ql, min(qr, m)), rt->qry(max(ql, m + 1ll), qr));
    }
};

struct DSU {
    /*
    DSU must include min and max index of the current component
    also, the updates for the values of each component must be separated
    into its own function

    so every time we update the value in the MinTree, we have to 
    call update on the corresponding value of the component in DSU
    */
    ll n;
    ll ncomps;
    vll par;
    vll csize;
    vll minc;
    vll cl; // left index of component
    vll cr; // right index of component
    ll curans;

    DSU(ll a_n, ll initans, const vll& a): n(a_n), ncomps(a_n), par(a_n, 0ll), csize(a_n, 1ll), minc(a_n, INF(ll)), cl(a_n, 0ll), cr(a_n, 0ll), curans(initans) {
        for(ll i = 0ll; i < n; i++) {
            cl[i] = cr[i] = par[i] = i;
            minc[i] = a[i];
        }
    }

    ll find(ll i) {
        return (i == par[i] ? i : par[i] = find(par[i]));
    }

    void unify(ll i, ll j, ParTree* ptr, MinTree* mtr, const vll& bpref) {
        ll pari = find(i);
        ll parj = find(j);

        if(pari == parj) return;

        ll prev_c = minc[pari] + minc[parj];

        ll npar;
        if(csize[pari] < csize[parj]) {
            // merge i into j
            npar = par[pari] = parj;
            csize[parj] += csize[pari];
        } else {
            // merge j into i
            npar = par[parj] = pari;
            csize[pari] += csize[parj];
        }
        cl[npar] = min(cl[pari], cl[parj]);
        cr[npar] = max(cr[pari], cr[parj]);

        minc[npar] = prev_c;

        upd(npar, ptr, mtr, bpref);
    }

    void upd(ll comp, ParTree* ptr, MinTree* mtr, const vll& bpref) {
        comp = find(comp);
        ll prval = minc[comp];

        // compute new cost
        // we must do casework on the size of the component
        ll cursz = csize[comp];

        if(cursz & 0b1ll) {
            // odd
            ll startpar = cl[comp] & 0b1ll;

            pll alt_min_pair = ptr->qry(cl[comp], cr[comp]);
            ll alt_min = (startpar ? alt_min_pair.second : alt_min_pair.first);

            minc[comp] = min(alt_min, mtr->qry(cl[comp], cr[comp])) + bpref[cr[comp] + 1ll] - bpref[cl[comp]];
        } else {
            // even
            minc[comp] = bpref[cr[comp] + 1ll] - bpref[cl[comp]];
            // cerr << "!! " << minc[comp] << endl;
        }
        
        // update total cost
        curans -= prval;
        curans += minc[comp];
    }
};

struct Query {
    ll qi, e;
};

typedef vector<Query> vq;
struct Artifact {
    ll w, a, b;
};

typedef vector<Artifact> va;

vll calculate_costs(vi w, vi a, vi b, vi e) {
    ll n = (ll)w.size();
    ll q = (ll)e.size();
    vll ans(q, 0);

    // Sorting queries into a vector for offline processing
    vq qs;
    
    for(ll i = 0ll; i < q; i++) {
        qs.pb({i, e[i]});
    }

    sort(qs.begin(), qs.end(), [](Query q1, Query q2) {return q1.e < q2.e;});

    // Storing artifacts in new format and sorting
    va arts;

    for(ll i = 0ll; i < n; i++) {
        arts.pb({w[i], a[i], b[i]});
    }

    sort(arts.begin(), arts.end(), [](Artifact v1, Artifact v2) {return v1.w < v2.w;});

    // Creating prefsum arrays for a and b

    vll prefa(n + 1ll, 0ll);

    for(ll i = 0ll; i < n; i++) {
        prefa[i + 1ll] = prefa[i] + arts[i].a;
    }

    vll prefb(n + 1ll, 0ll);

    for(ll i = 0ll; i < n; i++) {
        prefb[i + 1ll] = prefb[i] + arts[i].b;
    }

    // Creating vec of (diff, ind) pairs for updating MinTree
    vpll mintrupds;

    for(ll i = 1ll; i < n - 1ll; i++) {
        mintrupds.pb({arts[i + 1ll].w - arts[i - 1ll].w, i});
    }

    /// sort mintrupds by INCREASING order
    sort(mintrupds.begin(), mintrupds.end());

    // creating vec of (diff, ind) pairs for updating DSU
    vpll dsuupds;
    for(ll i = 0ll; i < n - 1ll; i++) {
        dsuupds.pb({arts[i + 1ll].w - arts[i].w, i});
    }

    sort(dsuupds.begin(), dsuupds.end());

    // Building Segtrees and DSU
    /// Building a[i] - b[i]
    vll amb(n, 0ll);
    for(ll i = 0ll; i < n; i++) amb[i] = arts[i].a - arts[i].b;

    /// building partree
    ParTree* ptr = new ParTree(0ll, n - 1ll);
    ptr->build(amb);

    /// mintree should store a[i] - b[i], initially INF
    MinTree* mtr = new MinTree(0ll, n - 1ll);
    vll mtrinit(n, INF(ll));
    mtrinit[0ll] = arts[0ll].a - arts[0ll].b;
    mtrinit[n - 1ll] = arts[n - 1ll].a - arts[n - 1ll].b;
    mtr->build(mtrinit);

    /// building DSU
    vll art_a_vals(n, 0ll);
    for(ll i = 0ll; i < n; i++) art_a_vals[i] = arts[i].a;
    DSU dsu(n, prefa[n], art_a_vals);

    // Answering queries offline
    ll qi = 0ll;
    ll mtrupdind = 0ll;
    ll dsuupdind = 0ll;

    while(qi < q) {
        ll curd = qs[qi].e;

        // update the DSU
        while(dsuupdind < n - 1ll && dsuupds[dsuupdind].first <= curd) {
            // cerr << "! " << dsuupds[dsuupdind].first << endl;
            ll updind = dsuupds[dsuupdind].second;
            dsu.unify(updind, updind + 1ll, ptr, mtr, prefb);
            dsuupdind++;
        }
        
        // update the MinTree
        while(mtrupdind < n - 2ll && mintrupds[mtrupdind].first <= curd) {
            ll updind = mintrupds[mtrupdind].second;
            mtr->upd(updind, arts[updind].a - arts[updind].b);
            
            dsu.upd(dsu.find(updind), ptr, mtr, prefb);
            mtrupdind++;
            
        }

        // answer
        ans[qs[qi].qi] = dsu.curans;
        
        qi++;
    }

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18