Submission #284045

#	Time	Username	Problem	Language	Result	Execution time	Memory
284045		Patrusheva_Anna	XORanges (eJOI19_xoranges)	C++17	0 / 100	12 ms	744 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
freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#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 < a.size()) ka *= 2;

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

    for (int i = ka; i < ka + 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 + 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 /= 2;
                if (l % 2 == 1)
                    cout << F_a(1, 1, ka, l / 2, l + kol) << "\n";
                else
                    cout << F_b(1, 1, kb, l / 2, l + kol) << "\n";
            }
        }
    }




    return 0;

}

Compilation message (stderr)

xoranges.cpp: In function 'int32_t main()':
xoranges.cpp:123:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     while (ka < a.size()) ka *= 2;
      |            ~~~^~~~~~~~~~
xoranges.cpp:126:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     while (kb < b.size()) kb *= 2;
      |            ~~~^~~~~~~~~~
xoranges.cpp:128:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int i = ka; i < ka + a.size(); i++)
      |                      ~~^~~~~~~~~~~~~~~
xoranges.cpp:136:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i = kb; i < kb + b.size(); i++)
      |                      ~~^~~~~~~~~~~~~~~
xoranges.cpp:102:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  102 | freopen("input.txt","r",stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
xoranges.cpp:103:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  103 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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