oj.uz

Submission #761739

# Submission time Handle Problem Language Result Execution time Memory
761739 2023-06-20T08:31:17 Z caganyanmaz Distributing Candies (IOI21_candies) C++17
100 / 100
 2366 ms 39112 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 0 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1195 ms 32416 KB Output is correct
2 Correct 1474 ms 36484 KB Output is correct
3 Correct 1513 ms 36316 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 193 ms 30052 KB Output is correct
3 Correct 718 ms 3888 KB Output is correct
4 Correct 2366 ms 38324 KB Output is correct
5 Correct 2146 ms 38744 KB Output is correct
6 Correct 854 ms 39112 KB Output is correct
7 Correct 843 ms 38452 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 296 KB Output is correct
3 Correct 94 ms 32584 KB Output is correct
4 Correct 280 ms 4152 KB Output is correct
5 Correct 973 ms 36012 KB Output is correct
6 Correct 880 ms 36592 KB Output is correct
7 Correct 561 ms 37076 KB Output is correct
8 Correct 1016 ms 35744 KB Output is correct
9 Correct 2238 ms 37304 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 0 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 1195 ms 32416 KB Output is correct
7 Correct 1474 ms 36484 KB Output is correct
8 Correct 1513 ms 36316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 193 ms 30052 KB Output is correct
11 Correct 718 ms 3888 KB Output is correct
12 Correct 2366 ms 38324 KB Output is correct
13 Correct 2146 ms 38744 KB Output is correct
14 Correct 854 ms 39112 KB Output is correct
15 Correct 843 ms 38452 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 94 ms 32584 KB Output is correct
19 Correct 280 ms 4152 KB Output is correct
20 Correct 973 ms 36012 KB Output is correct
21 Correct 880 ms 36592 KB Output is correct
22 Correct 561 ms 37076 KB Output is correct
23 Correct 1016 ms 35744 KB Output is correct
24 Correct 2238 ms 37304 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 338 ms 4264 KB Output is correct
27 Correct 195 ms 32600 KB Output is correct
28 Correct 1145 ms 36964 KB Output is correct
29 Correct 1055 ms 37356 KB Output is correct
30 Correct 994 ms 37592 KB Output is correct
31 Correct 888 ms 37744 KB Output is correct
32 Correct 701 ms 37944 KB Output is correct