Submission #868533

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868533	2023-10-31T16:58:52 Z	borisAngelov	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	239 ms	212588 KB

apple

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int maxRange = 1000000000;

struct DynamicSegmentTree
{
    struct Node
    {
        int lChild;
        int rChild;
        long long sum;

        Node()
        {
            lChild = -1;
            rChild = -1;
            sum = 0;
        }
    };

    Node tree[64 * maxn];
    bool lazy[64 * maxn];

    int cntNodes = 0;

    void build()
    {
        cntNodes = 1;
        tree[1].lChild = -1;
        tree[1].rChild = -1;
        tree[1].sum = 0;
    }

    void addLeftChild(int node)
    {
        ++cntNodes;
        tree[node].lChild = cntNodes;

        tree[cntNodes].lChild = -1;
        tree[cntNodes].rChild = -1;
        tree[cntNodes].sum = 0;
    }

    void addRightChild(int node)
    {
        ++cntNodes;
        tree[node].rChild = cntNodes;

        tree[cntNodes].lChild = -1;
        tree[cntNodes].rChild = -1;
        tree[cntNodes].sum = 0;
    }

    void pushLazy(int node, int l, int r)
    {
        if (lazy[node] == true)
        {
            tree[node].sum = r - l + 1;

            if (l != r)
            {
                if (tree[node].lChild == -1)
                {
                    addLeftChild(node);
                }

                if (tree[node].rChild == -1)
                {
                    addRightChild(node);
                }

                lazy[tree[node].lChild] = true;
                lazy[tree[node].rChild] = true;
            }

            lazy[node] = false;
        }
    }

    void update(int node, int l, int r, int ql, int qr)
    {
        pushLazy(node, l, r);

        if (l > qr || r < ql)
        {
            return;
        }

        if (ql <= l && r <= qr)
        {
            lazy[node] = true;
            pushLazy(node, l, r);
            return;
        }

        int mid = (l + r) / 2;

        if (tree[node].lChild == -1)
        {
            addLeftChild(node);
        }

        if (tree[node].rChild == -1)
        {
            addRightChild(node);
        }

        update(tree[node].lChild, l, mid, ql, qr);
        update(tree[node].rChild, mid + 1, r, ql, qr);

        tree[node].sum = tree[tree[node].lChild].sum + tree[tree[node].rChild].sum;
    }

    int query(int node, int l, int r, int ql, int qr)
    {
        pushLazy(node, l, r);

        if (r < ql || l > qr)
        {
            return 0;
        }

        if (ql <= l && r <= qr)
        {
            return tree[node].sum;
        }

        int mid = (l + r) / 2;

        if (tree[node].lChild == -1)
        {
            addLeftChild(node);
        }

        if (tree[node].rChild == -1)
        {
            addRightChild(node);
        }

        return query(tree[node].lChild, l, mid, ql, qr) + query(tree[node].rChild, mid + 1, r, ql, qr);
    }

    void update(int l, int r)
    {
        update(1, 1, maxRange, l, r);
    }

    int query(int l, int r)
    {
        return query(1, 1, maxRange, l, r);
    }
};

DynamicSegmentTree tree;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    int q;
    cin >> q;

    int c = 0;
    tree.build();

    while (q--)
    {
        int type, l, r;
        cin >> type >> l >> r;

        if (type == 2)
        {
            tree.update(l + c, r + c);
        }
        else
        {
            c = tree.query(l + c, r + c);
            cout << c << "\n";
        }
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	201664 KB	Output is correct
2	Correct	32 ms	201556 KB	Output is correct
3	Correct	31 ms	201552 KB	Output is correct
4	Correct	38 ms	201556 KB	Output is correct
5	Correct	39 ms	201548 KB	Output is correct
6	Correct	39 ms	201560 KB	Output is correct
7	Correct	39 ms	201560 KB	Output is correct
8	Correct	88 ms	203956 KB	Output is correct
9	Correct	158 ms	204116 KB	Output is correct
10	Correct	159 ms	206160 KB	Output is correct
11	Correct	168 ms	206112 KB	Output is correct
12	Correct	170 ms	206232 KB	Output is correct
13	Correct	147 ms	206172 KB	Output is correct
14	Correct	146 ms	206220 KB	Output is correct
15	Correct	239 ms	210436 KB	Output is correct
16	Correct	204 ms	212416 KB	Output is correct
17	Correct	151 ms	208208 KB	Output is correct
18	Correct	159 ms	208296 KB	Output is correct
19	Correct	211 ms	212560 KB	Output is correct
20	Correct	211 ms	212588 KB	Output is correct