Submission #761738

#	Time	Username	Problem	Language	Result	Execution time	Memory
761738		caganyanmaz	Distributing Candies (IOI21_candies)	C++17	0 / 100	343 ms	49760 KiB

candies

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define int int64_t
using namespace std;

constexpr static int INF = 1e18;

struct SegTree
{
	struct Node
	{
		int sum, min_prefix, max_prefix, min_index, max_index;	
		Node(int sum,int min_prefix,int max_prefix,int index):sum(sum), min_prefix(min_prefix), max_prefix(max_prefix), min_index(index), max_index(index) {}
		Node() : Node(0, INF, -INF, -1) {}
	};

	static Node merge(Node l, Node r)
	{
		Node new_node;
		if (l.min_prefix < r.min_prefix + l.sum)
		{
			new_node.min_index = l.min_index;
			new_node.min_prefix = l.min_prefix;
		}
		else
		{
			new_node.min_index = r.min_index;
			new_node.min_prefix = r.min_prefix + l.sum;
		}
		if (l.max_prefix > r.max_prefix + l.sum)
		{
			new_node.max_index = l.max_index;
			new_node.max_prefix = l.max_prefix;
		}
		else
		{
			new_node.max_index = r.max_index;
			new_node.max_prefix = r.max_prefix + l.sum;
		}
		new_node.sum = l.sum + r.sum;
		return new_node;
	}

	int n;
	vector<Node> data;
	SegTree(int n) : n(n), data(n<<2) {}
	void set(int l, int r, int index, int i, int val)
	{
		if (i >= r || l > i)
			return;
		if (l + 1 == r)
		{
			data[index] = Node(val, val, val, i);
			return;
		}
		int mid = (l+r)>>1;
		set(l, mid, index<<1, i, val);
		set(mid, r, index<<1|1, i, val);
		data[index] = merge(data[index<<1], data[index<<1|1]);
	}
	Node get(int l, int r, int index, int ss, int ee) const
	{
		if (l >= ee || ss >= r)
			return Node();
		if (ee >= r && l >= ss)
			return data[index];
		int mid = (l+r)>>1;
		Node l_node = get(l, mid, index<<1, ss, ee);
		Node r_node = get(mid, r, index<<1|1, ss, ee);
		return merge(l_node, r_node);
	}
	void set(int i, int val) { set(0, n, 1, i, val); }
	Node get(int ss, int ee) const { return get(0, n, 1, ss, ee); }
	int find_smallest_distance(int cap)
	{
		if (data[1].max_prefix - data[1].min_prefix <= cap)
			return -1;
		int l = 0, r = n, index = 1;
		int min_prefix = INF, max_prefix = -INF, sum = 0;
		while (r - l > 1)
		{
			int r_sum = data[index<<1].sum + sum;
			int r_max = max(data[index<<1|1].max_prefix + r_sum, max_prefix);
			int r_min = min(data[index<<1|1].min_prefix + r_sum, min_prefix);
			if (r_max - r_min > cap)
			{
				l = (l+r)>>1;
				sum = r_sum;
				index = index<<1|1;
			}
			else
			{
				r = (l+r)>>1;
				min_prefix = r_min;
				max_prefix = r_max;
				index = index<<1;
			}
		}
		return l;
	}

};

vector<array<int,2>> index_sort(const vector<int32_t>& v)
{
	vector<array<int, 2>> res(v.size());
	for (int i = 0; i < v.size(); i++)
		res[i] = {v[i], i};
	sort(res.begin(), res.end());
	return res;
}

vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v)
{
	for (int32_t& i : r) i++;
	vector<array<int,2>> li = index_sort(l), ri = index_sort(r);
	int n = v.size()+1;
	int m = c.size();
	int ll = 0, rr = 0;
	SegTree st(n);
	vector<int32_t> res(m);

	for (int i = 0; i < m; i++)
	{
		while (ll < li.size() && li[ll][0] == i) 
		{
			int index = li[ll++][1];
			st.set(index+1, v[index]);
		}
		while (rr < ri.size() && ri[rr][0] == i)
		{
			int index = ri[rr++][1];
			st.set(index+1, 0);
		}
		int ss = st.find_smallest_distance(c[i]);
		if (ss == -1)
		{
			int min_index = st.get(0, n).min_index;
			res[i] = st.get(min_index + 1, n).sum;
		}
		else
		{
			int a = st.get(ss, n).min_index,
			b = st.get(ss, n).max_index;
			if (a > b)
				res[i] = st.get(a+1, n).sum;
			else
				res[i] = c[i] + st.get(b+1, n).sum;
		}
	}
	return res;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<std::array<long int, 2> > index_sort(const std::vector<int>&)':
candies.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:127:13: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   while (ll < li.size() && li[ll][0] == i)
      |          ~~~^~~~~~~~~~~
candies.cpp:132:13: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   while (rr < ri.size() && ri[rr][0] == i)
      |          ~~~^~~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33