Submission #908800

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
908800	2024-01-16T21:51:43 Z	raphaelp	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	173 ms	3216 KB

apple

#include <bits/stdc++.h>
using namespace std;
int milliard = 1073741823;
class SegmentTree
{
private:
    vector<int> st, left, right;
    int cur = 1;
    int l(int x)
    {
        if (left[x] != -1)
            return left[x];
        left[x] = cur++;
        left.push_back(-1);
        right.push_back(-1);
        st.push_back(0);
        return left[x];
    }
    int r(int x)
    {
        if (right[x] != -1)
            return right[x];
        right[x] = cur++;
        left.push_back(-1);
        right.push_back(-1);
        st.push_back(0);
        return right[x];
    }
    void update(int a, int b, int L, int R, int x)
    {
        if (L > b || R < a)
            return;
        if (a <= L && b >= R)
            st[x] = R - L + 1;
        else
        {
            int m = (L + R) / 2;
            if (st[l(x)] != m - L + 1)
                update(a, b, L, m, l(x));
            if (st[r(x)] != R - m)
                update(a, b, m + 1, R, r(x));
            st[x] = st[l(x)] + st[r(x)];
        }
    }
    int RSQ(int a, int b, int L, int R, int x)
    {
        if (L > b || R < a)
            return 0;
        if (a <= L && b >= R)
            return st[x];
        if (st[x] == R - L + 1)
            return min(R, b) - max(a, L) + 1;
        int tot = 0, m = (L + R) / 2;
        if (left[x] != -1)
            tot += RSQ(a, b, L, m, l(x));
        if (right[x] != -1)
            tot += RSQ(a, b, m + 1, R, r(x));
        return tot;
    }

public:
    SegmentTree()
    {
        st.assign(1, 0);
        left.assign(1, -1);
        right.assign(1, -1);
    }
    void update(int a, int b)
    {
        update(a, b, 0, milliard, 0);
    }
    int RSQ(int a, int b)
    {
        return RSQ(a, b, 0, milliard, 0);
    }
};
int main()
{
    int M;
    cin >> M;
    SegmentTree ST;
    int C = 0;
    for (int i = 0; i < M; i++)
    {
        int a, l, r;
        cin >> a >> l >> r;
        if (a == 2)
        {
            ST.update(l + C, r + C);
        }
        else
        {
            C = ST.RSQ(l + C, r + C);
            cout << C << '\n';
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	11 ms	348 KB	Output is correct
5	Correct	14 ms	604 KB	Output is correct
6	Correct	14 ms	620 KB	Output is correct
7	Correct	14 ms	604 KB	Output is correct
8	Correct	65 ms	1464 KB	Output is correct
9	Correct	130 ms	2536 KB	Output is correct
10	Correct	130 ms	2380 KB	Output is correct
11	Correct	150 ms	2548 KB	Output is correct
12	Correct	130 ms	2376 KB	Output is correct
13	Correct	152 ms	3216 KB	Output is correct
14	Correct	173 ms	2896 KB	Output is correct
15	Correct	135 ms	2900 KB	Output is correct
16	Correct	134 ms	2976 KB	Output is correct
17	Correct	143 ms	3108 KB	Output is correct
18	Correct	144 ms	2756 KB	Output is correct
19	Correct	155 ms	3012 KB	Output is correct
20	Correct	137 ms	3160 KB	Output is correct