Submission #779258

#	Time	Username	Problem	Language	Result	Execution time	Memory
779258		vmanz	XORanges (eJOI19_xoranges)	C++14	100 / 100	412 ms	8644 KiB

xoranges

#include <iostream>
#include <vector>

using namespace std;

void actual(vector<int> &aib, int p, int nou, int vechi)
{
    int n = (int)aib.size() - 1;
    while (p <= n)
    {
        aib[p] ^= vechi;
        aib[p] ^= nou;
        p += (p & -p);
    }
}

int interogare(vector<int> &aib, int p)
{
    int rez = 0;
    while (p != 0)
    {
        rez ^= aib[p];
        p -= (p & -p);
    }
    return rez;
}

/*
void scrie_aib(vector<int> &aib)
{
    int n = (int)aib.size() - 1;
    for (int i = 1; i <= n; i++)
    {
        cout << i << ":\t" << aib[i] << "\n";
    }
    cout << "\n";
}
*/

int main()
{
    int n, q;
    cin >> n >> q;
    vector <int> v(n+1), aib_par(n+1, 0), aib_impar(n+1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        if (i % 2 == 0)
        {
            actual(aib_par, i, v[i], 0);
        }
        else
        {
            actual(aib_impar, i, v[i], 0);
        }
    }
    //scrie_aib(aib_par);
    //scrie_aib(aib_impar);
    for (int i = 0; i < q; i++)
    {
        int tip;
        cin >> tip;
        if (tip == 1)
        {
            int poz, val_nou;
            cin >> poz >> val_nou;
            if (poz % 2 == 0)
            {
                actual(aib_par, poz, val_nou, v[poz]);
                v[poz] = val_nou;
                //scrie_aib(aib_par);
            }
            else
            {
                actual(aib_impar, poz, val_nou, v[poz]);
                v[poz] = val_nou;
                //scrie_aib(aib_impar);
            }
        }
        else
        {
            int st, dr;
            cin >> st >> dr;
            int rez = 0;
            if ((dr - st + 1) % 2 == 0)
            {
                cout << rez << "\n";
            }
            else
            {
                if (st % 2 == 0)
                {
                    rez = (interogare(aib_par, dr) ^ interogare(aib_par, st - 1));
                }
                else
                {
                    rez = (interogare(aib_impar, dr) ^ interogare(aib_impar, st - 1));
                }
                cout << rez << "\n";
            }
        }
    }
    return 0;
}

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