Submission #868533

#	Time	Username	Problem	Language	Result	Execution time	Memory
868533		borisAngelov	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	239 ms	212588 KiB

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 / 100