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
#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';
        }
    }
}
# 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