Submission #436041

#	Time	Username	Problem	Language	Result	Execution time	Memory
436041		dacin21	Distributing Candies (IOI21_candies)	C++17	100 / 100	619 ms	27116 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33