Submission #1176783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176783		chikien2009	XORanges (eJOI19_xoranges)	C++20	100 / 100	84 ms	7752 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

class SEGMENT_TREE
{
    private:
    int tree_size;
    vector<pair<int, int>> tree;

    inline void Set(int ind, int l, int r, int x, int y)
    {
        if (r < x || x < l)
        {
            return;
        }
        if (l == r)
        {
            tree[ind] = {y * (l & 1), y * (!(l & 1))};
            return;
        }
        int m = (l + r) >> 1;
        Set(ind << 1, l, m, x, y);
        Set(ind << 1 | 1, m + 1, r, x, y);
        tree[ind].first = tree[ind << 1].first ^ tree[ind << 1 | 1].first;
        tree[ind].second = tree[ind << 1].second ^ tree[ind << 1 | 1].second;
    }
    inline pair<int, int> Get(int ind, int l, int r, int x, int y)
    {
        if (r < x || y < l)
        {
            return {0, 0};
        }
        if (x <= l && r <= y)
        {
            return tree[ind];
        }
        int m = (l + r) >> 1;
        pair<int, int> p1 = Get(ind << 1, l, m, x, y);
        pair<int, int> p2 = Get(ind << 1 | 1, m + 1, r, x, y);
        return {p1.first ^ p2.first, p1.second ^ p2.second};
    }
    public:
    inline SEGMENT_TREE(int new_size)
    {
        tree_size = new_size;
        tree.clear();
        tree.resize(tree_size << 2, {0, 0});
    }
    inline void Set(int x, int y)
    {
        Set(1, 1, tree_size, x, y);
    }
    inline pair<int, int> Get(int x, int y)
    {
        return Get(1, 1, tree_size, x, y);
    }
} st(200000);

int n, q, a, b, c;
pair<int, int> x, y;

int main()
{
    setup();

    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a;
        st.Set(i, a);
    }
    while (q--)
    {
        cin >> b;
        if (b == 1)
        {
            cin >> b >> c;
            st.Set(b, c);
        }
        else
        {
            cin >> b >> c;
            a = c - b + 1;
            if (a & 1)
            {
                if (b & 1)
                {
                    cout << st.Get(b, c).first << "\n";
                }
                else
                {
                    cout << st.Get(b, c).second << "\n";
                }
            }
            else
            {
                cout << 0 << "\n";
            }
        }
    }
    return 0;
}

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