oj.uz

Submission #760526

# Submission time Handle Problem Language Result Execution time Memory
760526 2023-06-17T17:36:03 Z fakeaccount3169 Distributing Candies (IOI21_candies) C++17
100 / 100
 2490 ms 39220 KB 
        #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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 6 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 32412 KB Output is correct
2 Correct 1484 ms 36492 KB Output is correct
3 Correct 1715 ms 36336 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 197 ms 30092 KB Output is correct
3 Correct 721 ms 6080 KB Output is correct
4 Correct 2490 ms 38348 KB Output is correct
5 Correct 2166 ms 38744 KB Output is correct
6 Correct 786 ms 39220 KB Output is correct
7 Correct 842 ms 38468 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 99 ms 30188 KB Output is correct
4 Correct 280 ms 4136 KB Output is correct
5 Correct 984 ms 35916 KB Output is correct
6 Correct 865 ms 36600 KB Output is correct
7 Correct 535 ms 37196 KB Output is correct
8 Correct 1038 ms 35940 KB Output is correct
9 Correct 2242 ms 37308 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 1169 ms 32412 KB Output is correct
7 Correct 1484 ms 36492 KB Output is correct
8 Correct 1715 ms 36336 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 197 ms 30092 KB Output is correct
11 Correct 721 ms 6080 KB Output is correct
12 Correct 2490 ms 38348 KB Output is correct
13 Correct 2166 ms 38744 KB Output is correct
14 Correct 786 ms 39220 KB Output is correct
15 Correct 842 ms 38468 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 99 ms 30188 KB Output is correct
19 Correct 280 ms 4136 KB Output is correct
20 Correct 984 ms 35916 KB Output is correct
21 Correct 865 ms 36600 KB Output is correct
22 Correct 535 ms 37196 KB Output is correct
23 Correct 1038 ms 35940 KB Output is correct
24 Correct 2242 ms 37308 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 327 ms 4156 KB Output is correct
27 Correct 178 ms 32700 KB Output is correct
28 Correct 1126 ms 36980 KB Output is correct
29 Correct 1018 ms 37372 KB Output is correct
30 Correct 1010 ms 37604 KB Output is correct
31 Correct 885 ms 37760 KB Output is correct
32 Correct 686 ms 37856 KB Output is correct