Submission #1190209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190209		theyeia	Nile (IOI24_nile)	C++20	100 / 100	149 ms	21696 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using tl = tuple<ll,ll,ll>;
const ll INF = 1e9 + 7;
#define F first
#define S second
#define sor(x) sort(begin(x), end(x))
#define FOR(i, a, b) for (int i = a; i < b; i++)



// Variables
int n, q, p = 2;
ll ans = 0;
tl id = {INF, INF, INF};

vector<pl> Art, Queries, Dif, Dif2;
vector<tl> Sg;

vi Link, Left, Right;
vl Ans, SavedCosts;



// Combine function
tl f(tl x, tl y) {
    return {min(get<0>(x), get<0>(y)),  min(get<1>(x), get<1>(y)),  min(get<2>(x), get<2>(y))};
}

// Builds segment tree and union find
void build() {
    // Segment tree
    while (p < n) p *= 2;
    Sg.resize(2 * p, id);
    Sg[0] = {0, 0, 0};

    for (int i = p; i < 2 * p; i++) {
        ll val0 = (i % 2) ? INF : Art[i - p].S;
        ll val1 = (i % 2) ? Art[i - p].S : INF;
        Sg[i] = {val0, val1, INF};
    }

    for (int i = p - 1; i > 0; i--) {
        Sg[i] = f(Sg[2 * i], Sg[2 * i + 1]);
    }

    // Union-find
    Link.resize(n, 0);
    Left.resize(n, 0);
    Right.resize(n, 0);
    SavedCosts.resize(n, 0);

    FOR(i, 0, n) {
        Link[i] = i;
        Left[i] = i;
        Right[i] = i;
        SavedCosts[i] = Art[i].S;
    }

    Ans.resize(q, 0);
}

// Point updates
void update(int index, ll value, int lo, int hi, int node) {
    if (hi < index || index < lo) return;
    if (lo == hi) {
        Sg[node] = {get<0>(Sg[node]), get<1>(Sg[node]), value};
        return;
    }

    int mid = (lo + hi) / 2;

    update(index, value, lo, mid, 2 * node);
    update(index, value, mid + 1, hi, 2 * node + 1);

    Sg[node] = f(Sg[2 * node], Sg[2 * node + 1]);
}

// Range minimum query
ll query(int l, int r, int lo, int hi, int node, int mode) {
    if (hi < l || r < lo) return INF;
    if (l <= lo && hi <= r) {
        if (mode == 0) return get<0>(Sg[node]);
        if (mode == 1) return get<1>(Sg[node]);
        if (mode == 2) return get<2>(Sg[node]);
    }

    int mid = (lo + hi) / 2;

    return min(query(l, r, lo, mid, 2 * node, mode), query(l, r, mid + 1, hi, 2 * node + 1, mode));
}



// Returns cost to process range (ONLY CALL ON REPRESENTATIVES)
ll cost(int u) {
    if ((Right[u] - Left[u]) % 2) return 0;

    ll a = query(Left[u], Right[u], 0, p - 1, 1, 2);
    ll b = query(Left[u], Right[u], 0, p - 1, 1, Left[u] % 2);

    return min(a, b);
}

// Find function with path compression
int find(int u) {
    return (u == Link[u]) ? u : Link[u] = find(Link[u]);
}

void unite(int u, int v) {
    ans -= SavedCosts[u] + SavedCosts[v];

    if (Left[v] - Left[v] > Right[u] - Left[u]) swap(u, v);

    Link[v] = u;

    Left[u] = min(Left[u], Left[v]);
    Right[u] = max(Right[u], Right[v]);

    SavedCosts[u] = cost(u);
    ans += SavedCosts[u];
}



// Reads input
void read(vi W, vi A, vi B, vi E) {
    n = W.size();
    q = E.size();

    Art.resize(n, {2 * INF, INF});

    FOR(i, 0, n) {
        ll w = (ll)W[i], a = (ll)A[i], b = (ll)B[i];
        Art.push_back({w, a - b});
        ans += a;
    }
    sor(Art);


    FOR(i, 0, n - 1) {
        Dif.push_back({Art[i + 1].F - Art[i].F, i});
        if (0 < i) Dif2.push_back({Art[i + 1].F - Art[i - 1].F, i});
    }
    sor(Dif);
    sor(Dif2);


    FOR(i, 0, q) {
        ll e = (ll)E[i];
        Queries.push_back({e, i});
    }
    sor(Queries);
}





// Main function
vl calculate_costs(vi W, vi A, vi B, vi E) {
    read(W, A, B, E);
    build();

    //for (auto a : Art) cout << "(" << a.F << "," << a.S << ") "; cout << endl;
    //for (auto s : Sg) cout << "(" << get<0>(s) << "," << get<1>(s) << "," << get<2>(s) << ") "; cout << endl;
    //cout << query(0, 0, 0, p - 1, 1, 0) << " " << query(0, 0, 0, p - 1, 1, 1) << " " << query(0, 0, 0, p - 1, 1, 2) << endl;

    int r1 = 0, r2 = 0;
    FOR(i, 0, q) {
        ll d = Queries[i].F;

        while (r2 < n - 2 && Dif2[r2].F <= d) {
            int u = Dif2[r2].S;
            update(u, Art[u].S, 0, p - 1, 1);
            r2++;

            u = find(u);

            ans -= SavedCosts[u];
            SavedCosts[u] = cost(u);
            ans += SavedCosts[u];
        }

        while (r1 < n - 1 && Dif[r1].F <= d) {
            int u = Dif[r1].S;

            unite(find(u), find(u + 1));
            r1++;
        }

        //FOR(s, 0, n) cout << find(s) << " "; cout << endl;
        //FOR(s, 0, n) cout << "(" << Left[s] << "," << Right[s] << ") "; cout << endl;
        //FOR(s, 0, n) cout << cost(find(s)) << " "; cout << endl;

        //cout << r1 << " " << r2 << endl;

        //for (auto s : Sg) cout << "(" << get<0>(s) << "," << get<1>(s) << "," << get<2>(s) << ") "; cout << endl;
        //cout << endl;

        Ans[Queries[i].S] = ans;
    }
    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