oj.uz

Submission #436041

# Submission time Handle Problem Language Result Execution time Memory
436041 2021-06-24T06:37:37 Z dacin21 Distributing Candies (IOI21_candies) C++17
100 / 100
 619 ms 27116 KB 
#include "candies.h"

#include <bits/stdc++.h>
using ll = int64_t;
using namespace std;
//really fast iterative segment-tree implementation

template<class Segtree_Data>
struct Segment_Tree{
	using T = typename Segtree_Data::node_t;
	int n;
	vector<T>data;
	Segment_Tree(int n_) : n(n_), data(2*n, Segtree_Data::node_init()){
		for(int i=n-1;i>=0;--i) data[i] = Segtree_Data::merge_nodes(data[i<<1], data[i<<1|1]);
	}
	Segment_Tree(vector<T> const&base) :  n(base.size()), data(2*n, Segtree_Data::node_init()){
		copy(base.begin(), base.end(), data.begin()+n);
		for(int i=n-1;i>=0;--i) data[i] = Segtree_Data::merge_nodes(data[i<<1], data[i<<1|1]);
	}
	void update(int pos, typename Segtree_Data::update_t const&val){
		for(Segtree_Data::update_node(data[pos+=n], val); pos>>=1;){
			data[pos] = Segtree_Data::merge_nodes(data[pos<<1], data[pos<<1|1]);
		}
	}
    void u(int pos, typename Segtree_Data::update_t const&val){
        return update(pos,val);
    }
	T query(int l, int r) const {
		T retL = Segtree_Data::node_ne(), retR = Segtree_Data::node_ne();
		for(l+=n, r+=n; l<r; l>>=1, r>>=1){
			if(l&1) retL = Segtree_Data::merge_nodes(retL, data[l++]);
			if(r&1) retR = Segtree_Data::merge_nodes(data[--r], retR);
		}
		return Segtree_Data::merge_nodes(retL, retR);
	}
    T q(int l, int r) const {
        return query(l, r);
    }
};
constexpr ll inf = 2e18;
struct Node{
    ll sum, min, max;
};
struct Segtreedata{
    typedef Node node_t;
    typedef int update_t;
    static constexpr node_t node_init() {return Node{0, 0, 0};}
    static constexpr node_t node_ne() {return Node{0, inf, -inf};}
    static node_t merge_nodes(node_t const&left, node_t const&right){
        return node_t{
            left.sum + right.sum,
            min(left.min, left.sum+right.min),
            max(left.max, left.sum+right.max)
        };
    }
    static void update_node(node_t &node, update_t const&update){
        node = node_t{update, min(update, 0), max(update, 0)};
    }
};
using Segtree = Segment_Tree<Segtreedata>;


vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    const int n = c.size();
    const int q = l.size();
    vector<int> ret(n);
    vector<vector<int> > ev(n+1);
    for(int i=0; i<q; ++i){
        ev[l[i]].push_back(i);
        ev[r[i]+1].push_back(-1-i);
    }
    Segtree st(q);
    for(int i=0; i<n; ++i){
        for(auto const&e:ev[i]){
            //cerr << "up " << e << "\n";
            if(e >= 0) st.u(e, v[e]);
            else st.u(-1-e, 0);
        }
        int l = 0, r = q+1;
        auto span = st.q(0, q);
        if(span.max - span.min <= c[i]){
            // start at 0 -> won't hit top boundary -> ans is sum - min
            ret[i] = span.sum - span.min;
            continue;
        }
        while(l+1 < r){
            const int m = l + (r-l) / 2;
            span = st.q(m, q);
            if(span.max - span.min <= c[i]){
                r = m;
            } else {
                l = m;
            }
        }
        span = st.q(l, q);
        //cerr << span.min << " " << span.max << " " << span.sum << "\n";
        assert(span.min == 0 || span.max == 0);
        if(span.min == 0){
            // won't hit bottom boundary -> ans is sum - max + c
            ret[i] = span.sum - span.max + c[i];
        } else {
            // won't hit top boundary
            ret[i] = span.sum - span.min;
        }
    }

    return ret;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 27036 KB Output is correct
2 Correct 619 ms 27076 KB Output is correct
3 Correct 597 ms 27016 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 198 ms 16604 KB Output is correct
3 Correct 135 ms 7484 KB Output is correct
4 Correct 587 ms 26984 KB Output is correct
5 Correct 589 ms 26948 KB Output is correct
6 Correct 514 ms 27064 KB Output is correct
7 Correct 494 ms 26948 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 92 ms 16192 KB Output is correct
4 Correct 101 ms 7500 KB Output is correct
5 Correct 263 ms 23216 KB Output is correct
6 Correct 262 ms 23120 KB Output is correct
7 Correct 258 ms 23232 KB Output is correct
8 Correct 253 ms 23344 KB Output is correct
9 Correct 403 ms 23232 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 586 ms 27036 KB Output is correct
7 Correct 619 ms 27076 KB Output is correct
8 Correct 597 ms 27016 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 198 ms 16604 KB Output is correct
11 Correct 135 ms 7484 KB Output is correct
12 Correct 587 ms 26984 KB Output is correct
13 Correct 589 ms 26948 KB Output is correct
14 Correct 514 ms 27064 KB Output is correct
15 Correct 494 ms 26948 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 92 ms 16192 KB Output is correct
19 Correct 101 ms 7500 KB Output is correct
20 Correct 263 ms 23216 KB Output is correct
21 Correct 262 ms 23120 KB Output is correct
22 Correct 258 ms 23232 KB Output is correct
23 Correct 253 ms 23344 KB Output is correct
24 Correct 403 ms 23232 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 97 ms 7616 KB Output is correct
27 Correct 182 ms 16708 KB Output is correct
28 Correct 554 ms 27044 KB Output is correct
29 Correct 517 ms 27116 KB Output is correct
30 Correct 587 ms 27008 KB Output is correct
31 Correct 506 ms 26988 KB Output is correct
32 Correct 474 ms 27076 KB Output is correct