Submission #284054

#	Time	Username	Problem	Language	Result	Execution time	Memory
284054		Patrusheva_Anna	XORanges (eJOI19_xoranges)	C++14	100 / 100	157 ms	9276 KiB

xoranges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")

#define ll long long
#define pb push_back
#define F first
#define S second
#define ull unsigned long long
#define pii pair < int, int >
#define ld long double


using namespace std;
using namespace __gnu_pbds;

mt19937 gen(time(0));
template <typename T>
using ordered_set=tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 100000 * 5;
int ta[N];
int tb[N];

void change_a(int v, int tl, int tr, int in ,int val)
{
    if (tl >= in && tr<= in)
    {
        ta[v] = val;
        return;
    }

    if (tl > in || tr < in) return;
    int mid = (tl + tr) / 2;

    change_a(v * 2, tl, mid, in , val);
    change_a(v * 2 + 1, mid + 1, tr, in , val);

    ta[v] = ta[v * 2] ^ ta[v * 2 + 1];
    return;
}

void change_b(int v, int tl, int tr, int in ,int val)
{
    if (tl >= in && tr<= in)
    {
        tb[v] = val;
        return;
    }

    if (tl > in || tr < in) return;
    int mid = (tl + tr) / 2;

    change_b(v * 2, tl, mid, in , val);
    change_b(v * 2 + 1, mid + 1, tr, in , val);

    tb[v] = tb[v * 2] ^ tb[v * 2 + 1];
    return;
}

int F_a(int v, int tl, int tr, int l, int r)
{
    if (tl >= l && tr <= r)
    {
        return ta[v];
    }
    if (tl > r || tr < l) return 0;
    int mid = (tl + tr) / 2;

    return F_a(v * 2, tl, mid, l, r) ^ F_a(v * 2 + 1, mid + 1, tr, l, r);

}

int F_b(int v, int tl, int tr, int l, int r)
{
    if (tl >= l && tr <= r)
    {
        return tb[v];
    }
    if (tl > r || tr < l) return 0;
    int mid = (tl + tr) / 2;

    return F_b(v * 2, tl, mid, l, r) ^ F_b(v * 2 + 1, mid + 1, tr, l, r);

}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#else

#endif


    int n;
    cin >> n;
    int q;
    cin >> q;

    vector < int > a, b;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (i % 2 == 0) a.pb(x);
        else b.pb(x);
    }


    int ka = 1;
    while (ka < (int)a.size()) ka *= 2;

    int kb = 1;
    while (kb < (int)b.size()) kb *= 2;

    for (int i = ka; i < ka + (int)a.size(); i++)
        ta[i] = a[i - ka];

    for (int i = ka - 1; i >= 1; i--)
        ta[i] = ta[i * 2] ^ ta[i * 2 + 1];



    for (int i = kb; i < kb + (int)b.size(); i++)
        tb[i] = b[i - kb];

    for (int i = kb - 1; i >= 1; i--)
        tb[i] = tb[i * 2] ^ tb[i * 2 + 1];


    while (q--)
    {
        int z;
        cin >> z;
        if (z == 1)
        {
            int in, val;
            cin >> in >> val;
            if (in % 2 == 1)
            {
                change_a(1, 1, ka, in / 2 + 1, val);
            }
            else
                change_b(1, 1, kb, in / 2, val);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            if ((r - l + 1) % 2 == 0) cout << 0 << "\n";
            else
            {
                int kol = r - l + 1;
                kol = kol % 2 + kol / 2;
                if (l % 2 == 1)
                    cout << F_a(1, 1, ka, 1 + l / 2, l / 2 + kol) << "\n";
                else
                    cout << F_b(1, 1, kb, l / 2, l / 2 + kol - 1) << "\n";

//                cout << l % 2 + l / 2 << ' ' << kol + l / 2  - (1 - l % 2)<< "\n";
            }
        }
    }




    return 0;

}

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