oj.uz

Submission #436219

# Submission time Handle Problem Language Result Execution time Memory
436219 2021-06-24T10:33:14 Z Popax21 Distributing Candies (IOI21_candies) C++17
8 / 100
 484 ms 23104 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 23104 KB Output is correct
2 Correct 484 ms 22980 KB Output is correct
3 Correct 443 ms 22976 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -