Submission #1247238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247238		colossal_pepe	Nile (IOI24_nile)	C++20	32 / 100	77 ms	15288 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = 1e12;

int n, q;
vector<pair<int, int>> queries;
vector<int> idx, w;
vector<ll> a, b;
vector<tuple<int, int, int>> edges;
ll ans;

struct DSU {
    struct Node {
        int e;
        ll tot, tot_b, lover, rover, meven, modd;
        Node() { }
        Node(int i) {
            e = -1;
            tot = a[idx[i]];
            tot_b = b[idx[i]];
            lover = rover = a[idx[i]] - b[idx[i]];
            meven = modd = INF;
        }
    };
    vector<Node> t;
    DSU() {
        t.resize(n);
        for (int i = 0; i < n; i++) {
            t[i] = Node(i);
            ans += t[i].tot;
        }
    }
    int find(int x) {
        return (t[x].e < 0 ? x : t[x].e = find(t[x].e));
    }
    void update(int x) {
        ans -= t[x].tot;
        if (t[x].e % 2) {
            t[x].tot = t[x].tot_b + min(t[x].lover, t[x].rover);
            t[x].tot = min(t[x].tot, t[x].tot_b + (t[x].lover % 2 ? t[x].meven : t[x].modd));
        } else t[x].tot = t[x].tot_b;
        ans += t[x].tot;
    }
    void mergeFar(int i) {
        i++;
        ll m = a[idx[i]] - b[idx[i]];
        // cerr << "WOW " << i << ' ' << m << endl;
        int x = find(i);
        if (i % 2) t[x].modd = min(t[x].modd, m);
        else t[x].meven = min(t[x].meven, m);
        update(x);
    }
    void mergeClose(int i) {
        int x = find(i), y = find(i + 1);
        if (-t[x].e < -t[y].e) swap(x, y);
        ans -= t[y].tot;
        t[x].tot_b += t[y].tot_b;
        if (x < y) t[x].rover = t[y].rover;
        else t[x].lover = t[y].lover;
        t[x].meven = min(t[x].meven, t[y].meven);
        t[x].modd = min(t[x].modd, t[y].modd);
        t[x].e += t[y].e, t[y].e = x;
        update(x);
    }
};

void prep() {
    idx.resize(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) {
        return w[i] < w[j];
    });
}

void makeEdges() {
    for (int i = 0; i + 1 < n; i++) {
        edges.emplace_back(w[idx[i + 1]] - w[idx[i]], i + 1, i);
        if (i + 2 < n) edges.emplace_back(w[idx[i + 2]] - w[idx[i]], i + 2, i);
    }
    sort(edges.rbegin(), edges.rend());
}


vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {

    n = (int)W.size();
    w = W;
    a.assign(A.begin(), A.end());
    b.assign(B.begin(), B.end());
    prep();

    DSU dsu = DSU();

    makeEdges();

    q = (int)E.size();
    queries.resize(q);
    for (int i = 0; i < q; i++) {
        queries[i] = make_pair(E[i], i);
    }
    sort(queries.begin(), queries.end());

    vector<ll> ret(q);
    for (auto [d, qi] : queries) {
        // cerr << "PROCESSING " << qi << endl;
        while (not edges.empty() and get<0>(edges.back()) <= d) {
            auto [_, j, i] = edges.back();
            edges.pop_back();
            // cerr << "BEFORE " << i << ' ' << j << ' ' << ans << endl;
            if (i == j - 1) dsu.mergeClose(i);
            else dsu.mergeFar(i);
            // cerr << "AFTER " << ans << endl;
        }
        ret[qi] = ans;
    }
    return ret;
}

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