Submission #1229674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229674		boris_mihov	Nile (IOI24_nile)	C++20	100 / 100	141 ms	18192 KiB

nile

#include "nile.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 17;
const llong INF = 1e18;

int n;
struct SegmentTreeMIN
{
	llong tree[4*MAXN];
	void build(int l, int r, int node, llong v[], int t)
	{
		if (l == r)
		{
			if (t == (l & 1)) tree[node] = v[l];
			else tree[node] = INF;
			return;
		}

		int mid = l + r >> 1;
		build(l, mid, 2*node, v, t);
		build(mid + 1, r, 2*node + 1, v, t);
		tree[node] = std::min(tree[2*node], tree[2*node + 1]);
	}
	
	void update(int l, int r, int node, int queryPos, llong queryVal)
	{
		if (l == r)
		{
			tree[node] = queryVal;
			return;
		}
		
		int mid = l + r >> 1;
		if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
		else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
		tree[node] = std::min(tree[2*node], tree[2*node + 1]);
	}

	llong query(int l, int r, int node, int queryL, int queryR)
	{
		if (queryL <= l && r <= queryR)
		{
			return tree[node];
		}

		int mid = l + r >> 1;
		llong res = INF;

		if (queryL <= mid) res = std::min(res, query(l, mid, 2*node, queryL, queryR));
		if (mid + 1 <= queryR) res = std::min(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
		return res;
	}

	void build(llong v[], int t)
	{
		build(1, n, 1, v, t);
	}

	void update(int idx, llong val)
	{
		update(1, n, 1, idx, val);
	}	

	llong query(int l, int r)
	{
		return query(1, n, 1, l, r);
	}
};

struct Fenwick
{
	int tree[MAXN];
	void build()
	{
		for (int i = 1 ; i <= n ; ++i)
		{
			tree[i]++;
			if (i + (i & (-i)) <= n) tree[i + (i & (-i))] += tree[i];
		}
	}

	void update(int idx, int val)
	{
		for (; idx <= n ; idx += idx & (-idx))
		{
			tree[idx] += val;
		}
	}

	int query(int idx)
	{
		int res = 0;
		for (; idx ; idx -= idx & (-idx))
		{
			res += tree[idx];
		}

		return res;
	}

	int findKth(int k)
	{
		int idx = 0;
		for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
		{
			if (idx + (1 << lg) <= n && tree[idx + (1 << lg)] < k)
			{
				idx += (1 << lg);
				k -= tree[idx];
			}
		}

		return idx + 1;
	}
};

struct Delivery
{
	int a, b, w;
	friend bool operator < (const Delivery &a, const Delivery &b)
	{
		return a.w < b.w;
	}
};

struct Query
{
	int d, idx;
	friend bool operator < (const Query &a, const Query &b)
	{
		return a.d < b.d;
	}
};

std::vector <std::pair <int,int>> queryBarriers;
std::vector <std::pair <int,int>> barriers;
std::vector <Query> queries;
SegmentTreeMIN treeFull[2];
SegmentTreeMIN treeAdd[2];
llong prefix[MAXN];
Delivery s[MAXN];
Fenwick fenwick;

llong rangeQuery(int l, int r)
{
	llong sum = prefix[r] - prefix[l - 1];
	if ((r - l + 1) % 2 == 0)
	{
		return sum;
	}

	if (l == r)
	{
		return s[l].a;
	}

	llong ans = sum + treeFull[l & 1].query(l, r);
	if (l + 1 <= r) ans = std::min(ans, sum + treeAdd[(l + 1) & 1].query(l, r));
	return ans;
}

llong v[MAXN];
std::vector <long long> calculate_costs(std::vector <int> W, std::vector <int> A, std::vector <int> B, std::vector <int> E)
{
	n = W.size();
	for (int i = 1 ; i <= n ; ++i)
	{
		s[i].w = W[i - 1];
		s[i].a = A[i - 1];
		s[i].b = B[i - 1];
	}

	std::sort(s + 1, s + 1 + n);
	for (int i = 1 ; i <= n ; ++i)
	{
		prefix[i] = prefix[i - 1] + s[i].b;
	}	

	for (int i = 2 ; i <= n ; ++i)
	{
		barriers.push_back({s[i].w - s[i - 1].w, i});
	}

	for (int i = 2 ; i < n ; ++i)
	{
		queryBarriers.push_back({s[i + 1].w - s[i - 1].w, i});
	}

	int idx = 0;
	std::vector <llong> sol(E.size());
	for (const int &d : E)
	{
		queries.push_back({d, idx++});
	}

	std::sort(queries.begin(), queries.end());
	std::sort(barriers.begin(), barriers.end());
	std::sort(queryBarriers.begin(), queryBarriers.end());
	fenwick.build();

	std::fill(v + 1, v + 1 + n, INF);
	treeAdd[0].build(v, 0);
	treeAdd[1].build(v, 1);

	for (int i = 2 ; i <= n ; i += 2)
	{
		v[i] = s[i].a - s[i].b;
	}

	treeFull[0].build(v, 0);
	std::fill(v + 1, v + 1 + n, INF);

	for (int i = 1 ; i <= n ; i += 2)
	{
		v[i] = s[i].a - s[i].b;
	}
	
	treeFull[1].build(v, 1);
	
	int ptrBar = 0;
	int ptrQBar = 0;
	llong answer = 0;
	for (int i = 1 ; i <= n ; ++i)
	{
		answer += s[i].a;
	}

	for (const auto &[d, idx] : queries)
	{
		while (ptrBar < barriers.size() && barriers[ptrBar].first <= d)
		{
			int pos = barriers[ptrBar].second;
			int cnt = fenwick.query(pos);
			int left = fenwick.findKth(cnt - 1);
			int right = fenwick.findKth(cnt + 1) - 1;
			answer -= rangeQuery(left, pos - 1);
			answer -= rangeQuery(pos, right);
			answer += rangeQuery(left, right);
			fenwick.update(pos, -1);
			ptrBar++;
		}
		
		while (ptrQBar < queryBarriers.size() && queryBarriers[ptrQBar].first <= d)
		{
			int pos = queryBarriers[ptrQBar].second;
			int cnt = fenwick.query(pos);
			int left = fenwick.findKth(cnt);
			int right = fenwick.findKth(cnt + 1) - 1;
			answer -= rangeQuery(left, right);
			treeAdd[pos & 1].update(pos, s[pos].a - s[pos].b);
			answer += rangeQuery(left, right);
			ptrQBar++;
		}

		sol[idx] = answer;
	}

	return sol;
}

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