Submission #1122569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122569		Mousa_Aboubaker	Nile (IOI24_nile)	C++17	38 / 100	247 ms	32216 KiB

nile

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

const int inf = 1e9 + 1;

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
	vector<int> w = W, a = A, b = B, e = E;
	int n = w.size(), q = e.size();
	vector<tuple<int, int, int>> d(n);
	for(int i = 0; i < n; i++)
		d[i] = make_tuple(w[i], a[i], b[i]);
	sort(d.begin(), d.end());
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int l, int r)
			{
				return w[l] < w[r];
			});
	vector<int> lg(n + 1);
	lg[1] = 0;
	for(int i = 2; i <= n; i++)
		lg[i] = lg[i >> 1] + 1;
	vector spt(n, vector<int>(21));
	for(int i = 0; i < n; i++)
		spt[i][0] = i;
	for(int j = 1; j < 21; j++)
		for(int i = 0; i + (1 << (j - 1)) < n; i++)
		{
			int x = spt[i][j - 1], y = spt[i + (1 << (j - 1))][j - 1];
			if(get<1>(d[x]) - get<2>(d[x]) < get<1>(d[y]) - get<2>(d[y]))
				spt[i][j] = x;
			else
				spt[i][j] = y;
			// spt[i + (1 << (j - 1))][j] = min(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
		}
	auto get_min = [&](int l, int r) -> int
	{
		int j = lg[r - l + 1];
		int x = spt[l][j], y = spt[r - (1 << j) + 1][j];
		if(get<1>(d[x]) - get<2>(d[x]) < get<1>(d[y]) - get<2>(d[y]))
			return x;
		else
			return y;
		// return min(spt[l][j], spt[r - (1 << j) + 1][j]);
	};
	map<int, vector<int>, greater<int>> mp1;
	map<int, int> res;
	for(int i = 1; i < n; i++)
		mp1[get<0>(d[i]) - get<0>(d[i - 1])].push_back(i);
	map<int, long long> dp;
	long long sum = accumulate(b.begin(), b.end(), 0ll);
	if(n & 1)
	{
		int x = get_min(0, n - 1);
		sum += get<1>(d[x]) - get<2>(d[x]);
	}
	dp[inf] = sum;
	set<pair<int, int>> lst;
	lst.insert({0, n - 1});
	int lst_idx = inf;
	for(auto [f, s]: mp1)
	{
		for(auto i: s)
		{
			auto it = prev(lst.lower_bound({i + 1, -1}));
			auto [ff, ss] = *it;
			lst.erase(it);
			lst.insert({ff, i - 1});
			lst.insert({i, ss});
			int len1 = ss - ff + 1;
			int len2 = i - ff;
			int len3 = ss - i + 1;
			if(!(len1 & 1))
			{
				int x = get_min(ff, i - 1), y = get_min(i, ss);
				int z = get_min(ff, ss);
				if(len2 & 1)
					dp[f] += (get<1>(d[x]) - get<2>(d[x])) + (get<1>(d[y]) - get<2>(d[y]));
			}
			else
			{
				int x = get_min(ff, i - 1), y = get_min(i, ss);
				// cout << ff << ' ' << i << ' ' << ss << ' ' << x << ' ' << y << '\n';
				int z = get_min(ff, ss);
				long long add = -(get<1>(d[z]) - get<2>(d[z]));
				if(len2 & 1)
					add += get<1>(d[x]) - get<2>(d[x]);
				else
					add += get<1>(d[y]) - get<2>(d[y]);
				dp[f] += add;
			}
		}
		//cout << f << '\n';
		//for(auto [f, s]: lst)
		//{
		//	cout << f << ' ' << s << '\n';
		//}
		dp[f] += dp[lst_idx];
		lst_idx = f;
	}
	vector<long long> fin(q);
	for(int i = 0; i < q; i++)
	{
		fin[i] = dp.upper_bound(e[i])->second;
	}
	return fin;
}

• 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: 15 / 15
• Subtask 7: 0 / 18