Submission #1122566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122566		Mousa_Aboubaker	Nile (IOI24_nile)	C++17	38 / 100	223 ms	31000 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<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] = ord[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(a[x] - b[x] < a[y] - b[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(a[x] - b[x] < a[y] - b[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[w[ord[i]] - w[ord[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 += a[x] - b[x];
		// cout << x << ' ' << a[x] - b[x] << '\n';
	}
	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.upper_bound({i, -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);
				if(len2 & 1)
					dp[f] += (a[x] - b[x]) + (a[y] - b[y]);
			}
			else
			{
				int x = get_min(ff, i - 1), y = get_min(i, ss);
				int z = get_min(ff, ss);
				int add = -(a[z] - b[z]);
				if(len2 & 1)
					add += a[x] - b[x];
				else
					add += a[y] - b[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