Submission #1323630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323630		kaloyan	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	20 ms	47352 KiB

apple

#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000 + 10;
const int MAXLOG = 30;
const int INF = 1e9 + 10;

int n, c;
struct DynamicSegmentTree
{
    struct Node
    {
        int sum;
        int left;
        int right;
        bool lazy;

        Node()
        {
            sum = 0;
            left = 0;
            right = 0;
            lazy = 0;
        }

        void assign(const Node &left, const Node &right)
        {
            sum = left.sum + right.sum;
        }
    };

    int cnt = 1;
    Node tree[MAXLOG * MAXN];

    void push(int node, int l, int r)
    {
        if(!tree[node].lazy)
        {
            return;
        }

        tree[node].sum = r - l + 1;

        if(l != r)
        {
            if(tree[node].left == 0)
            {
                tree[node].left = ++cnt;
                
            }

            if(tree[node].right == 0)
            {
                tree[node].left = ++cnt;
            }

            tree[tree[node].left].lazy = 1;
            tree[tree[node].right].lazy = 1;
        }
        
        tree[node].lazy = 0;
    }

    void update(int node, int l, int r, int queryL, int queryR)
    {
        push(node, l, r);

        if(queryL <= l && r <= queryR)
        {
            tree[node].lazy = 1;
            push(node, l, r);
            return;
        }

        int mid = l + r >> 1;
        if(queryL <= mid)
        {
            if(tree[node].left == 0)
            {
                tree[node].left = ++cnt;
            }

            update(tree[node].left, l, mid, queryL, queryR);
        }

        if(mid + 1 <= queryR)
        {
            if(tree[node].right == 0)
            {
                tree[node].right = ++cnt;
            }

            update(tree[node].right, mid + 1, r, queryL, queryR);
        }

        tree[node].assign(tree[tree[node].left], tree[tree[node].right]);
    }

    int query(int node, int l, int r, int queryL, int queryR)
    {
        push(node, l, r);

        if(node == 0 || r < queryL || queryR < l)
        {
            return 0;
        }

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

        int res = 0;
        int mid = l + r >> 1;
        res += query(tree[node].left, l, mid, queryL, queryR);
        res += query(tree[node].right, mid + 1, r, queryL, queryR);
        return res;
    }

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

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

DynamicSegmentTree tree;

void solve()
{
    std::cin >> n;

    for(int i = 1 ; i <= n ; ++i)
    {
        int type, x, y;
        std::cin >> type >> x >> y;

        if(type == 1)
        {
            c = tree.query(x + c, y + c);
            std::cout << c << "\n";
        }
        else
        {
            tree.update(x + c, y + c);
        }
    }
}

void fastIO()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
}

int main()
{
    fastIO();
    solve();
    return 0;
}

• Subtask 1: 0 / 100