Submission #868531

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868531	2023-10-31T16:57:43 Z	borisAngelov	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	199 ms	109392 KB

apple

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	100956 KB	Output is correct
2	Correct	16 ms	100956 KB	Output is correct
3	Correct	15 ms	101128 KB	Output is correct
4	Correct	22 ms	101256 KB	Output is correct
5	Correct	24 ms	101208 KB	Output is correct
6	Correct	24 ms	101212 KB	Output is correct
7	Correct	24 ms	101212 KB	Output is correct
8	Correct	80 ms	104248 KB	Output is correct
9	Correct	155 ms	107384 KB	Output is correct
10	Correct	152 ms	107348 KB	Output is correct
11	Correct	154 ms	107428 KB	Output is correct
12	Correct	172 ms	107348 KB	Output is correct
13	Correct	134 ms	107992 KB	Output is correct
14	Correct	152 ms	107600 KB	Output is correct
15	Incorrect	199 ms	109392 KB	Output isn't correct
16	Halted	0 ms	0 KB	-