Submission #641709

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
641709	2022-09-17T13:25:32 Z	finn__	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	644 ms	207728 KB

apple

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

struct stnode
{
    unsigned t;
    bool 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 = (l->y - l->x + 1);
            l->z = 1;
            r->t = (r->y - r->x + 1);
            r->z = 1;
            z = 0;
        }
    }

    void incr(size_t i, size_t j)
    {
        if (x > j || y < i)
            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)
            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;
    long c = 0;

    for (size_t i = 0; i < m; i++)
    {
        long 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	304 KB	Output is correct
4	Correct	22 ms	4860 KB	Output is correct
5	Correct	27 ms	6004 KB	Output is correct
6	Correct	27 ms	5752 KB	Output is correct
7	Correct	27 ms	5964 KB	Output is correct
8	Correct	194 ms	44492 KB	Output is correct
9	Correct	384 ms	77180 KB	Output is correct
10	Correct	400 ms	85428 KB	Output is correct
11	Correct	407 ms	91644 KB	Output is correct
12	Correct	410 ms	94428 KB	Output is correct
13	Correct	396 ms	109992 KB	Output is correct
14	Correct	396 ms	110976 KB	Output is correct
15	Correct	597 ms	201820 KB	Output is correct
16	Correct	593 ms	203212 KB	Output is correct
17	Correct	409 ms	114716 KB	Output is correct
18	Correct	409 ms	114816 KB	Output is correct
19	Correct	644 ms	207652 KB	Output is correct
20	Correct	617 ms	207728 KB	Output is correct