Submission #469360

#	Time	Username	Problem	Language	Result	Execution time	Memory
469360		myvaluska	XORanges (eJOI19_xoranges)	C++14	55 / 100	211 ms	6268 KiB

xoranges

// najsprostejsiasarica.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
// ejoiden2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
// trenujflashinka.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
// ejoiden2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int maxn = 1 << 17;
vector<int>l(maxn * 2);
vector<int>r(maxn * 2);
vector<int> xor1 (maxn * 2);
vector<int>xor2(maxn * 2);
void update(int i, int vr, int hod)
{
    if (i<l[vr] || i>r[vr])
    {
        return;
    }
    if (i == l[vr] && i == r[vr])
    {
        if (i % 2 == 0)
        {
            xor1[vr] = hod;
            return;
        }
        else
        {
            xor2[vr] = hod;
            return;
        }
    }
    update(i, vr * 2 + 1, hod);
    update(i, vr * 2 + 2, hod);
    xor1[vr] = xor1[vr * 2 + 1] ^ xor1[vr * 2 + 2];
    xor2[vr] = xor2[vr * 2 + 1] ^ xor2[vr * 2 + 2];
}
int xorusek1(int li, int ri, int vr)
{
    if (li > r[vr] || ri < l[vr])
    {
        return 0;
    }
    if (li <= l[vr] && ri >= r[vr])
    {
        return xor1[vr];
    }
    return xorusek1(li, ri, vr * 2 + 1) ^ xorusek1(li, ri, vr * 2 + 2);
}
int xorusek2(int li, int ri, int vr)
{
    if (li > r[vr] || ri < l[vr])
    {
        return 0;
    }
    if (li <= l[vr] && ri >= r[vr])
    {
        return xor2[vr];
    }
    return xorusek2(li, ri, vr * 2 + 1) ^ xorusek2(li, ri, vr * 2 + 2);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int q;
    cin >> q;
    vector<int>v(n);
    for (int i = maxn - 1; i < maxn * 2 - 1; i++)
    {
        l[i] = (i - maxn) + 1;
        r[i] = (i - maxn) + 1;
    }
    for (int i = maxn - 2; i >= 0; i--)
    {
        l[i] = l[i * 2 + 1];
        r[i] = r[i * 2 + 2];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        update(i, 0, v[i]);
    }
    while (q--)
    {
        int typ;
        cin >> typ;
        if (typ == 1)
        {
            int index;
            cin >> index;
            int hod;
            cin >> hod;
            index -= 1;
            update(index, 0, hod);
            v[index] = hod;
        }
        else if (typ == 2)
        {
            int lavy;
            cin >> lavy;
            int pravy;
            cin >> pravy;
            lavy -= 1;
            pravy -= 1;
            if(((pravy-lavy)+1)%2==0)
            {
                cout << 0 << '\n';
            }
            else if (pravy == lavy)
            {
                cout << v[lavy] << '\n';
            }
            else
            {
                if (lavy % 2 == 0)
                {
                    cout << xorusek1(lavy, pravy, 0) << '\n';
                }
                else if(lavy%2==1)
                {
                    cout << xorusek2(lavy, pravy, 0) << '\n';
                }
            }
        }
    }
    return 0;
    //std::cout << "Hello World!\n";
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started:
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file file

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