Submission #761739

#	Time	Username	Problem	Language	Result	Execution time	Memory
761739		caganyanmaz	Distributing Candies (IOI21_candies)	C++17	100 / 100	2366 ms	39112 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 MEMORY_FACTOR = 3;
            constexpr static int INF = 1e18;
             
             
             
            struct SegTree
            {
            	struct Node
            	{
            		int sum, min_prefix, max_prefix;
            		Node(int sum, int min_prefix, int max_prefix) : sum(sum), min_prefix(min_prefix), max_prefix(max_prefix) {}
            		bool check(int capacity) {return max_prefix - min_prefix > capacity; } 
            		Node() : Node(0, 0, 0) {}
             
            	};
             
            	static Node merge(Node l, Node r)
            	{
            		return Node(l.sum + r.sum, min(l.min_prefix, r.min_prefix + l.sum), max(l.max_prefix, r.max_prefix + l.sum));
            	}
             
            	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);
            			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(0, INF, -INF);
            		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); }
             
            };
             
            vector<array<int,2>> index_sort(const vector<int32_t>& v)
            {
            	vector<array<int, 2>> res(v.size());
            	for (int i = 0; i < static_cast<int64_t>(v.size()); i++)
            		res[i] = {v[i], i};
            	sort(res.begin(), res.end());
            	return res;
            }
             
             
            int find_min_prefix(const SegTree& st, int ss, int ee)
            {
            	int mp = st.get(ss, ee).min_prefix;
            	int l = ss, r = ee;
            	while (r - l > 1)
            	{
            		int m = (l+r)>>1;
            		if (st.get(ss, m).sum + st.get(m, ee).min_prefix == mp)
            			l = m;
            		else
            			r = m;
            	}
            	return l;
            }
             
            int find_max_prefix(const SegTree& st, int ss, int ee)
            {
            	int mp = st.get(ss, ee).max_prefix;
            	int l = ss, r = ee;
            	while (r - l > 1)
            	{
            		int m = (l+r)>>1;
            		if (st.get(ss, m).sum + st.get(m, ee).max_prefix == mp)
            			l = m;
            		else
            			r = m;
            	}
            	return l;
            }
             
            int find_smallest_distance(const SegTree& st, int cap, int n)
            {
            	int l = -1, r = n;
            	while (r - l > 1)
            	{
            		int m = (l+r)>>1;
            		if (st.get(m, n).check(cap))
            			l = m;
            		else
            			r = m;
            	}
            	return l;
            }
             
            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 < static_cast<int64_t>(li.size()) && li[ll][0] == i) 
            		{
            			int index = li[ll][1];
            			st.set(index+1, v[index]);
            			ll++;
            		}
            		while (rr < static_cast<int64_t>(ri.size()) && ri[rr][0] == i)
            		{
            			int index = ri[rr][1];
            			st.set(index+1, 0);
            			rr++;
            		}
            		int ss = find_smallest_distance(st, c[i], n);
            		if (ss == -1)
            		{
            			res[i] = st.get(find_min_prefix(st, 0, n) + 1, n).sum;
            		}
            		else
            		{
            			int a = find_min_prefix(st, ss, n),
            			b = find_max_prefix(st, ss, n);
            			if (a > b)
            				res[i] = st.get(a+1, n).sum;
            			else
            				res[i] = c[i] + st.get(b+1, n).sum;
            		}
            	}
            	return res;
            }

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