Submission #1214324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214324		badge881	XORanges (eJOI19_xoranges)	C++20	100 / 100	138 ms	18012 KiB

xoranges

#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<ll> st1, st2, I, D;

void updatePair(ll x, ll nod)
{
    st1[nod] = x;
    nod /= 2;
    while (nod > 0)
    {
        st1[nod] = st1[nod * 2] ^ st1[nod * 2 + 1];
        nod /= 2;
    }
}

void updateImpair(ll x, ll nod)
{
    st2[nod] = x;
    nod /= 2;
    while (nod > 0)
    {
        st2[nod] = st2[nod * 2] ^ st2[nod * 2 + 1];
        nod /= 2;
    }
}

ll calcPair(ll a, ll b, ll nod)
{
    if (I[nod] > b || D[nod] < a)
        return 0;
    if (I[nod] >= a && D[nod] <= b)
        return st1[nod];
    return calcPair(a, b, nod * 2) ^ calcPair(a, b, nod * 2 + 1);
}

ll calcImpair(ll a, ll b, ll nod)
{
    if (I[nod] > b || D[nod] < a)
        return 0;
    if (I[nod] >= a && D[nod] <= b)
        return st2[nod];
    return calcImpair(a, b, nod * 2) ^ calcImpair(a, b, nod * 2 + 1);
}

int main()
{
    ll n, i, j, k, q, x, pot = 1, tam, op, l, r;
    scanf("%lld %lld", &n, &q);
    while (pot < n)
        pot *= 2;
    st1.resize(pot * 2, 0);
    st2.resize(pot * 2, 0);
    I.resize(pot * 2);
    D.resize(pot * 2);
    for (i = 0; i < n; i++)
    {
        scanf("%lld", &x);
        if (i % 2 == 0)
            updatePair(x, i + pot);
        else
            updateImpair(x, i + pot);
    }
    for (i = pot; i < pot * 2; i++)
        I[i] = D[i] = i;
    for (i = pot - 1; i > 0; i--)
    {
        I[i] = I[i * 2];
        D[i] = D[i * 2 + 1];
    }
    while (q--)
    {
        scanf("%lld", &op);
        if (op == 1)
        {
            scanf("%lld %lld", &i, &x);
            i--;
            if (i % 2 == 0)
                updatePair(x, i + pot);
            else
                updateImpair(x, i + pot);
        }
        else
        {
            scanf("%lld %lld", &l, &r);
            tam = (r - l) + 1;
            l--;
            r--;
            if (tam % 2 == 0)
                cout << 0 << '\n';
            else
            {
                if (l % 2 == 0)

                    cout << calcPair(l + pot, r + pot, 1) << '\n';

                else

                    cout << calcImpair(l + pot, r + pot, 1) << '\n';
            }
        }
    }
    return 0;
}

Compilation message (stderr)

xoranges.cpp: In function 'int main()':
xoranges.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%lld %lld", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
xoranges.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%lld", &x);
      |         ~~~~~^~~~~~~~~~~~
xoranges.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%lld", &op);
      |         ~~~~~^~~~~~~~~~~~~
xoranges.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |             scanf("%lld %lld", &i, &x);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
xoranges.cpp:86:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |             scanf("%lld %lld", &l, &r);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~

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