Submission #1248188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248188		adrilen	Nile (IOI24_nile)	C++20	0 / 100	101 ms	21684 KiB

nile

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

constexpr ll maxn = 1e5;

struct Node {
    ll w, a, b;

    bool operator<(const auto &a) const {
        return w < a.w;
    }
};

constexpr ll siz = (1 << 17);
constexpr ll inf = (1ll << 60);

pair<ll, ll> odd[siz * 2], par[siz * 2];


pair<ll, ll> query(int p, int l, int r, int sl, int sr, bool er_odd)
{
    if (sl <= l && r <= sr) {
        if (er_odd) return odd[p];
        return par[p];
    }

    if (sl > r || sr < l) return {inf, -1};

    int mid = (l + r) / 2;
    return min(query(p * 2, l, mid, sl, sr, er_odd), query(p * 2 + 1, mid + 1, r, sl, sr, er_odd));
}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
    ll n = W.size();
    
    vector<Node> noder(n);
    for (ll i = 0; i < n; i++) noder[i] = {W[i], A[i], B[i]};
    sort(noder.begin(), noder.end());

    vector<Node> edges;
    for (ll i = 0; i < n - 1; i++) edges.push_back({noder[i+1].w - noder[i].w, i, i+1});
    sort(edges.begin(), edges.end());

    vector<pair<ll, ll>> d(E.size());
    for (int i = 0; i < (int) E.size(); i++) d[i] = {E[i], i};
    sort(d.begin(), d.end());

    for (int i = 0; i < n; i++)
    {
        if (i & 1) {
            odd[i + siz] = {A[i] - B[i], i};
            par[i + siz] = {inf, i};
        } else {
            odd[i + siz] = {inf, i};
            par[i + siz] = {A[i] - B[i], i};
        }
    }
    for (int y = n; y < siz; y++) odd[y + siz] = par[y + siz] = { inf, y};

    for (int i = siz - 1; i > 0; i--)
    {
        odd[i] = min(odd[i * 2], odd[i * 2 + 1]);
        par[i] = min(par[i * 2], par[i * 2 + 1]);
    }


    ll output = accumulate(A.begin(), A.end(), 0ll);
    vector<ll> svar(E.size());
    set<pair<ll, ll>> klumper;

    for (int i = 0; i < n; i++) klumper.insert({i, i});

    ll forbedring;
    int neste_kant = 0;
    for (auto [f, idx] : d)
    {
        while (neste_kant != n - 1 && edges[neste_kant].w <= f)
        {
            Node kant = edges[neste_kant++];
            
            pair<ll, ll> venstre = *prev(klumper.upper_bound({kant.a, inf})),
            hoyre = *klumper.lower_bound({kant.b, -1ll});
            
            if (venstre.first == venstre.second && hoyre.first == hoyre.second)
            {
                output += B[venstre.first] - A[venstre.first] + B[hoyre.first] - A[hoyre.first];

                klumper.erase(venstre);
                klumper.erase(hoyre);
                klumper.insert({venstre.first, hoyre.second});
            } else if (venstre.first == venstre.second)
            {
                bool venstre_odd = (venstre.first & 1);
                auto [val, ind] = query(1, 0, siz - 1, hoyre.first, hoyre.second, venstre_odd);
                forbedring = A[venstre.first] - B[venstre.first] - val;

                if (forbedring > 0)
                {
                    output -= forbedring;

                    klumper.erase(venstre);
                    klumper.erase(hoyre);
                    klumper.insert({venstre.first, ind - 1});
                    klumper.insert({ind, ind});
                    if (ind != hoyre.second) klumper.insert({ind + 1, hoyre.second});
                }
            } else if (hoyre.first == hoyre.second)
            {
                bool hoyre_odd = (hoyre.first & 1);
                auto [val, ind] = query(1, 0, siz - 1, venstre.first, venstre.second, hoyre_odd);
                forbedring = A[hoyre.first] - B[hoyre.first] - val;

                if (forbedring > 0)
                {
                    output -= forbedring;

                    klumper.erase(venstre);
                    klumper.erase(hoyre);
                    klumper.insert({ind + 1, hoyre.first});
                    klumper.insert({ind, ind});
                    if (ind != venstre.first) klumper.insert({venstre.first, ind + 1});
                }
            } else 
            {
                klumper.erase(venstre);
                klumper.erase(hoyre);
                klumper.insert({venstre.first, hoyre.second});
            }
        }

        svar[idx] = output;
    }

    return svar;
}

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