Submission #908800

#	Time	Username	Problem	Language	Result	Execution time	Memory
908800		raphaelp	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	173 ms	3216 KiB

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 / 100