Submission #641704

#	Time	Username	Problem	Language	Result	Execution time	Memory
641704		finn__	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	212 KiB

apple

#include <bits/stdc++.h>
using namespace std;

struct stnode
{
    unsigned t, z;
    stnode *l, *r;
    size_t x, y;

    stnode *new_node(bool left_child)
    {
        stnode *c = (stnode *)calloc(1, sizeof(stnode));

        if (left_child)
        {
            c->x = x;
            c->y = (x + y) / 2;
        }
        else
        {
            c->x = (x + y) / 2 + 1;
            c->y = y;
        }

        return c;
    }

    void check_children()
    {
        if (!l)
            l = new_node(1);
        if (!r)
            r = new_node(0);
    }

    void propagate()
    {
        check_children();
        if (z)
        {
            l->t = z * (l->y - l->x + 1);
            l->z = z;
            r->t = z * (r->y - r->x + 1);
            r->z = z;
            z = 0;
        }
    }

    void incr(size_t i, size_t j)
    {
        if (x > j || y < i || x > y)
            return;
        if (i <= x && y <= j)
        {
            t = (y - x + 1);
            z = 1;
        }
        else
        {
            propagate();
            l->incr(i, j);
            r->incr(i, j);
            t = l->t + r->t;
        }
    }

    unsigned range_sum(size_t i, size_t j)
    {
        if (x > j || y < i || x > y)
            return 0;
        if (i <= x && y <= j)
        {
            return t;
        }
        else
        {
            propagate();
            return l->range_sum(i, j) + r->range_sum(i, j);
        }
    }

    void destroy()
    {
        if (l)
        {
            l->destroy();
            free(l);
        }
        if (r)
        {
            r->destroy();
            free(r);
        }
    }
};

int main()
{
    size_t m;
    cin >> m;

    stnode *root = (stnode *)calloc(1, sizeof(stnode));
    root->y = 1000000000;
    size_t c = 0;

    for (size_t i = 0; i < m; i++)
    {
        size_t d, x, y;
        cin >> d >> x >> y;

        if (d == 1)
        {
            unsigned v = root->range_sum(x - 1 + c, y - 1 + c);
            cout << v << '\n';
            c += v;
        }
        else
        {
            root->incr(x - 1 + c, y - 1 + c);
        }
    }

    root->destroy();
}

• Subtask 1: 0 / 100