Submission #1134651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134651		alterio	Nile (IOI24_nile)	C++20	23 / 100	2097 ms	15792 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(x) (x).begin(), (x).end()

struct S {
	ll w, a, b;
};

bool csort(S a, S b) {
	if (a.w != b.w) return a.w < b.w;
	return a.a < b.a;
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int N = A.size(), Q = (int) E.size();
	vector<pair<ll, ll>> ord;
	for (int i = 0; i < Q; i++) ord.push_back({E[i], i});
	sort(all(ord));
	vector<S> V;
	for (int i = 0; i < N; i++) V.push_back({W[i], A[i], B[i]});
	sort(all(V), csort);
    vector<ll> res(Q, 0);
	ll ans = 0;
	set<pair<int, int>> s;
	s.insert({-1e6, -1e6});
	s.insert({1e6, 1e6});
	ll ANS[N + 2];
	for (int i = 0; i < N; i++) {
		s.insert({i, i});
		ANS[i] = V[i].a;
		ans += V[i].a;
	}
	ll prf[N + 2];
	memset(prf, 0, sizeof(prf));
	prf[0] = V[0].b;
	for (int i = 1; i < N; i++) prf[i] = prf[i - 1] + V[i].b;
	auto get = [&] (int l, int r) {
		if (l < 0 || r >= N || l > r) return 0LL;
		return prf[r] - (l == 0 ? 0 : prf[l - 1]);
	};
	for (auto x : ord) {
		vector<pair<int, int>> toDelete, toAdd;
		auto it = s.begin();
		it++;
		auto nxt = it;
		nxt++;
		vector<pair<int, int>> cont;
		while (1) {
			ll first = it->second, last = nxt->first;
			if (last == 1e6) break;
			if (V[last].w - V[first].w <= x.first) {
				if (!cont.size()) cont.push_back(*it), toDelete.push_back(*it), ans -= ANS[it->second];
				toDelete.push_back(*nxt);
				cont.push_back(*nxt);
				ans -= ANS[nxt->second];
			}
			else if (cont.size()) {
				int l = cont[0].first, r = cont.back().second;
				int len = r - l + 1;
				if (len % 2 == 0) toAdd.push_back({l, r}), ANS[r] = get(l, r);
				else {
					ll newAns = 1e15;
					for (int i = 0; i < cont.size(); i++) {
						int posL = cont[i].first, posR = cont[i].second;
						if ((posR - posL + 1) % 2 == 1) {
							ll sum = ANS[posR];
							sum += get(l, posL - 1);
							sum += get(posR + 1, r);
							newAns = min(newAns, sum);
						}
					}
					for (int i = 0; i < cont.size(); i++) {
						int posL = cont[i].first, posR = cont[i].second;
						if ((posR - posL + 1) % 2 == 0) continue;
						if (i) {
							if ((posL - l) % 2 == 0) newAns = min(newAns, get(l, posL - 1) + V[posL].a + get(posL + 1, r));
							else if (V[posL + 1].w - V[posL - 1].w <= x.first) newAns = min(newAns, get(l, posL - 1) + V[posL].a + get(posL + 1, r));
						}
						if (i + 1 < cont.size()) {
							if ((r - posR) % 2 == 0) newAns = min(newAns, get(l, posR - 1) + V[posR].a + get(posR + 1, r));
							else if (V[posR + 1].w - V[posR - 1].w <= x.first) newAns = min(newAns, get(l, posR - 1) + V[posR].a + get(posR + 1, r));
						}
					}
					toAdd.push_back({l, r});
					ANS[r] = newAns;
				}
				cont.clear();
			}
			it++;
			nxt++;
		}
		if (cont.size()) {
			int l = cont[0].first, r = cont.back().second;
			int len = r - l + 1;
			if (len % 2 == 0) toAdd.push_back({l, r}), ANS[r] = get(l, r);
			else {
				ll newAns = 1e15;
				for (int i = 0; i < cont.size(); i++) {
					int posL = cont[i].first, posR = cont[i].second;
					if ((posR - posL + 1) % 2 == 1) {
						ll sum = ANS[posR];
						sum += get(l, posL - 1);
						sum += get(posR + 1, r);
						newAns = min(newAns, sum);
					}
				}
				for (int i = 0; i < cont.size(); i++) {
					int posL = cont[i].first, posR = cont[i].second;
					if ((posR - posL + 1) % 2 == 0) continue;
					if (i) {
						if ((posL - l) % 2 == 0) newAns = min(newAns, get(l, posL - 1) + V[posL].a + get(posL + 1, r));
						else if (V[posL + 1].w - V[posL - 1].w <= x.first) newAns = min(newAns, get(l, posL - 1) + V[posL].a + get(posL + 1, r));
					}
					if (i + 1 < cont.size()) {
						if ((r - posR) % 2 == 0) newAns = min(newAns, get(l, posR - 1) + V[posR].a + get(posR + 1, r));
						else if (V[posR + 1].w - V[posR - 1].w <= x.first) newAns = min(newAns, get(l, posR - 1) + V[posR].a + get(posR + 1, r));
					}
				}
				toAdd.push_back({l, r});
				ANS[r] = newAns;
			}
			cont.clear();
		}
		for (auto el : toDelete) s.erase(el);
		for (auto el : toAdd) s.insert(el), ans += ANS[el.second];
		res[x.second] = ans;
	}
    return res;
}

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