Submission #919254

#	Time	Username	Problem	Language	Result	Execution time	Memory
919254		raphaelp	XORanges (eJOI19_xoranges)	C++14	100 / 100	467 ms	12588 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
class SegmentTree
{
private:
    vector<int> st;
    int N;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    void update(int pos, int val, int L, int R, int x)
    {
        if (pos < L || pos > R)
            return;
        if (L == R)
        {
            st[x] = val;
        }
        else
        {
            int m = (L + R) / 2;
            update(pos, val, L, m, l(x));
            update(pos, val, m + 1, R, r(x));
            st[x] = st[l(x)] ^ st[r(x)];
        }
    }
    int RSQ(int L, int R, int a, int b, int x)
    {
        if (L > b || R < a)
            return 0;
        if (L >= a && R <= b)
            return st[x];
        int m = (L + R) / 2;
        return RSQ(L, m, a, b, l(x)) ^
               RSQ(m + 1, R, a, b, r(x));
    }

public:
    SegmentTree(int x)
    {
        N = pow(2, ceil(log2(x)));
        st.assign(3 * N, 0);
    }
    void update(int pos, int val)
    {
        update(pos, val, 0, N - 1, 1);
    }
    int RSQ(int a, int b)
    {
        return RSQ(0, N - 1, a, b, 1);
    }
};
int main()
{
    int N, Q;
    cin >> N >> Q;
    SegmentTree odd(N), even(N);
    for (int i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        if (i % 2)
            odd.update(i, x);
        else
            even.update(i, x);
    }
    for (int i = 0; i < Q; i++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {

            int x, val;
            cin >> x >> val;
            x--;
            if (x % 2)
                odd.update(x, val);
            else
                even.update(x, val);
        }
        else
        {
            int a, b;
            cin >> a >> b;
            a--, b--;
            if ((b - a) % 2 == 1)
                cout << 0 << '\n';
            else
            {
                if (a % 2)
                    cout << odd.RSQ(a, b) << '\n';
                else
                    cout << even.RSQ(a, b) << '\n';
            }
        }
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25