Submission #1134619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134619		alterio	Nile (IOI24_nile)	C++20	6 / 100	75 ms	19248 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<ll, pair<ll, ll>>> s;
	s.insert({-1e10, {-1e10, 0}});
	s.insert({1e10, {1e10, 0}});
	for (int i = 0; i < N; i++) {
		s.insert({i, {i, V[i].a}});
		ans += V[i].a;
	}
	ll prf[N];
	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) {
		return prf[r] - (l == 0 ? 0 : prf[l - 1]);
	};
	for (auto x : ord) {
		vector<pair<ll, pair<ll, ll>>> toDelete, toAdd;
		auto it = s.begin();
		it++;
		vector<vector<pair<ll, pair<ll, ll>>>> cont;
		int cnt = 0;
		cont.push_back({});
		while (1) {
			if (it->first == 1e10) break;
			auto nxt = it;
			nxt++;
			ll first = it->second.first, last = nxt->first;
			if (last == 1e10) break;
			if (V[last].w - V[first].w <= x.first) {
				if (!cnt) cont.back().push_back(*it), toDelete.push_back(*it);
				toDelete.push_back(*nxt);
				cont.back().push_back(*nxt);
				cnt++;
			}
			else {
				cnt = 0;
				if (cont.back().size()) cont.push_back({});
			}
			it++;
		}
		for (auto v : cont) {
			if (!v.size()) continue;
			ll l = v[0].first, r = v.back().second.first;
			ll len = r - l + 1;
			if (len % 2 == 0) {
				toAdd.push_back({l, {r, get(l, r)}});
				continue;
			}
			ll newAns = 1e15;
			for (int i = 0; i < v.size(); i++) {
				ll sum = v[i].second.second;
				if (i) sum += get(l, v[i].first - 1);
				if (i < v.size() - 1) sum += get(v[i].second.first + 1, r);
				newAns = min(newAns, sum);
			}
			for (int i = 0; i < v.size() - 1; i++) {
				int pos = v[i].second.first;
				if (pos == l) continue;
				if (V[pos + 1].w - V[pos - 1].w <= x.first) newAns = min(newAns, get(l, pos - 1) + get(pos + 1, r) + V[pos].a);
			}
			toAdd.push_back({l, {r, newAns}});
		}
		for (auto el : toDelete) {
			s.erase(s.find(el));
			ans -= el.second.second;
		}
		for (auto el : toAdd) {
			s.insert(el);
			ans += el.second.second;
		}
		res[x.second] = ans;
	}
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 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