Submission #254111

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
254111	2020-07-29T11:07:12 Z	test2	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	68 ms	16532 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	16032 KB	Output is correct
2	Correct	8 ms	16000 KB	Output is correct
3	Correct	8 ms	16000 KB	Output is correct
4	Correct	12 ms	16000 KB	Output is correct
5	Correct	13 ms	16000 KB	Output is correct
6	Correct	14 ms	16000 KB	Output is correct
7	Correct	12 ms	16000 KB	Output is correct
8	Correct	30 ms	16128 KB	Output is correct
9	Correct	56 ms	16376 KB	Output is correct
10	Correct	56 ms	16412 KB	Output is correct
11	Correct	51 ms	16376 KB	Output is correct
12	Correct	54 ms	16376 KB	Output is correct
13	Correct	68 ms	16504 KB	Output is correct
14	Correct	59 ms	16504 KB	Output is correct
15	Correct	62 ms	16532 KB	Output is correct
16	Correct	61 ms	16504 KB	Output is correct
17	Correct	67 ms	16504 KB	Output is correct
18	Correct	56 ms	16504 KB	Output is correct
19	Correct	65 ms	16504 KB	Output is correct
20	Correct	53 ms	16504 KB	Output is correct