oj.uz

답안 #760520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760520 2023-06-17T17:20:21 Z fakeaccount3169 사탕 분배 (IOI21_candies) C++17
3 / 100
 5000 ms 32600 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 (l + 1 == r)
    			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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 10 ms 596 KB Output is correct
5 Correct 104 ms 596 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5054 ms 32356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 212 KB Output is correct
2 Execution timed out 5026 ms 30044 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 5061 ms 32600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 10 ms 596 KB Output is correct
5 Correct 104 ms 596 KB Output is correct
6 Execution timed out 5054 ms 32356 KB Time limit exceeded
7 Halted 0 ms 0 KB -