Submission #1107943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107943		sleepntsheep	Nile (IOI24_nile)	C++17	100 / 100	146 ms	19136 KiB

nile

#include "nile.h"
#include <vector>
#include <array>
#include <set>
#include <tuple>
#include <algorithm>

using namespace std;
using ll = long long;

vector<ll> calculate_costs(vector<int> W, vector<int> A,
                                       vector<int> B, vector<int> E) {
    vector<tuple<int, int, int> > a;
    int n = (int)W.size(), q = (int)E.size();

    for (int i = 0; i < n; ++i) a.emplace_back(W[i], A[i], B[i]);
    sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i) tie(W[i], A[i], B[i]) = a[i];

    ll base = 0, added = 0;
    for (int i = 0; i < n; ++i) base += B[i];

    vector<pair<int, int> > gap1, gap2;

    for (int i = 1; i < n; ++i) gap1.emplace_back(W[i] - W[i - 1], i - 1);
    for (int i = 2; i < n; ++i) gap2.emplace_back(W[i] - W[i - 2], i - 2);
    sort(gap1.begin(), gap1.end(), greater<>());
    sort(gap2.begin(), gap2.end(), greater<>());

    vector<pair<int, int> > E1;
    for (int i = 0; i < q; ++i) E1.emplace_back(E[i], i);
    sort(E1.begin(), E1.end());

    vector<ll> ans(q);

    struct Blk { 
	int l, r; ll pr[2], jmp;
	bool operator<(const Blk&o) const { return r < o.r; }
	ll cost() { return (l ^ r) % 2 ? 0ll : min({jmp, pr[l & 1]}); }
    };

    set<Blk> st;

    const ll oo = 1e18;

    for (int i = 0; i < n; ++i) {
	Blk b = {i, i, {oo, oo}, oo};
	b.pr[i & 1] = A[i] - B[i];
	st.insert(b);
	added += b.cost();
    }

    for (auto [QrE, QrEi] : E1) {
	while (gap1.size() && gap1.back().first <= QrE) {
	    auto i = gap1.back().second; gap1.pop_back();
	    auto it = st.lower_bound({0, i, {0, 0}, 0}), it2 = next(it);
	    auto b = *it, bRig = *it2;
	    st.erase(it); st.erase(it2);
	    added -= b.cost() + bRig.cost();
	    b.r = bRig.r;
	    for (auto x : {0, 1}) b.pr[x] = min(b.pr[x], bRig.pr[x]);
	    b.jmp = min(b.jmp, bRig.jmp);
	    st.insert(b);
	    added += b.cost();
	}
	while (gap2.size() && gap2.back().first <= QrE) {
	    auto i = gap2.back().second; gap2.pop_back();
	    auto it = st.lower_bound({0, i, {0, 0}, 0});
	    ll cst = A[i + 1] - B[i + 1];
	    if (it->jmp > cst) {
		auto b = *it; added -= b.cost(); b.jmp = cst;
		st.erase(it); st.insert(b);
		added += b.cost();
	    }
	}
	ans[QrEi] = base + added;
    }

    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