Submission #1122555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122555		Mousa_Aboubaker	Nile (IOI24_nile)	C++17	32 / 100	161 ms	17788 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();
	sort(w.begin(), w.end());
	map<int, vector<int>, greater<int>> mp1;
	map<int, int> res;
	for(int i = 1; i < n; i++)
		mp1[w[i] - w[i - 1]].push_back(i);
	map<int, int> dp;
	dp[inf] = n + (n & 1);
	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))
				if(len2 & 1)
					dp[f] += 2;
		}
		//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: 0 / 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