Submission #436219

#	Time	Username	Problem	Language	Result	Execution time	Memory
436219		Popax21	Distributing Candies (IOI21_candies)	C++17	8 / 100	484 ms	23104 KiB

candies

#include "candies.h"
#include <assert.h>
#include <stddef.h>
#include <vector>

typedef long long llong;

namespace vtree {
    struct node {
        int left, right;
        node *lchild, *rchild;
        llong val, lazy;
    } nodes[400000], *next_node = nodes;

    node *create_tree(int l, int r) {
        assert(l < r);

        node *n = next_node++;
        n->left = l;
        n->right = r;
        n->lazy = 0;

        if(l == r-1) {
            n->val = 0;
            n->lchild = NULL;
            n->rchild = NULL;
        } else {
            int m = l + (r - l) / 2;
            n->val = -1;
            n->lchild = create_tree(l, m);
            n->rchild = create_tree(m, r);
        }

        return n;
    }

    void apply_lazy(node *n) {
        n->val += n->lazy;
        if(n->lchild) n->lchild->lazy += n->lazy;
        if(n->rchild) n->rchild->lazy += n->lazy;
        n->lazy = 0;
    }

    llong query_tree(node *n, int p) {
        while(n->left != n->right-1) {
            apply_lazy(n);

            int m = n->left + (n->right - n->left) / 2;
            if(p < m) n = n->lchild;
            else n = n->rchild;
        }
        assert(n->left == p);

        apply_lazy(n);
        return n->val;
    }

    void update_tree(node *n, int l, int r, llong o) {
        apply_lazy(n);
        if(r <= n->left || n->right <= l) return;

        if(l <= n->left && n->right <= r) {
            n->lazy += o;
        } else {
            update_tree(n->lchild, l, r, o);
            update_tree(n->rchild, l, r, o);
        }
    }
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
    //Create the value tree
    vtree::node *vtree = vtree::create_tree(0, c.size());
    for(int i = 0; i < (int) l.size(); i++) vtree::update_tree(vtree, l[i], r[i]+1, v[i]);

    std::vector<int> answ(c.size());
    for(int i = 0; i < (int) c.size(); i++) {
        answ[i] = (int) std::min((llong) c[i], vtree::query_tree(vtree, i));
    }
    return answ;
}

• Subtask 1: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33