Submission #254111

#	Time	Username	Problem	Language	Result	Execution time	Memory
254111		test2	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	68 ms	16532 KiB

apple

#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 30);
int t, a, b, c;
int tree[2000006];
int nodes;
int le[2000006], ri[2000006];

int left(int x)
{
        if (le[x] == -1)
                le[x] = ++nodes;
        return le[x];
}

int right(int x)
{
        if (ri[x] == -1)
                ri[x] = ++nodes;
        return ri[x];
}

void update(int node, int L, int R, int l, int r)
{
        
        if (l > r || l > R || r < L || tree[node] == R - L + 1)
                return;

        if (L >= l && R <= r)
        {
                tree[node] = R - L + 1;
                return;
        }
        int mid = (L + R) >> 1;
        update(left(node), L, mid, l, r);
        update(right(node), mid + 1, R, l, r);
        if (le[node] == -1)
                tree[node] = tree[ri[node]];
        else if (ri[node] == -1)
                tree[node] = tree[le[node]];
        else
                tree[node] = tree[le[node]] + tree[ri[node]];
}

int query(int node, int L, int R, int l, int r)
{
        if (l > r || l > R || r < L || node == -1)
                return 0;

        if (L >= l && R <= r)
        {
                return tree[node];
        }

        if (tree[node] == R - L + 1)
        {
                return min(r, R) - max(l, L) + 1;
        }

        int mid = (L + R) >> 1;
        int s1 = query(le[node], L, mid, l, r);
        int s2 = query(ri[node], mid + 1, R, l, r);

        return s1 + s2;
}

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        memset(le, -1, sizeof le);
        memset(ri, -1, sizeof ri);
        //freopen("in.in", "r", stdin);

        cin >> t;
        int C = 0;
        while (t--)
        {
                int a, b, c;
                cin >> a >> b >> c;
                b += C;
                c += C;
                if (a == 1)
                {
                        int ans = query(0, 1, N, b, c);
                        C = ans;
                        cout << ans << "\n";
                }
                else
                {
                        update(0, 1, N, b, c);
                }
        }

        return 0;
}

• Subtask 1: 100 / 100