Submission #1177828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177828		Mousa_Aboubaker	XORanges (eJOI19_xoranges)	C++20	100 / 100	82 ms	12800 KiB

xoranges

#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <deque>
#include <climits>
#include <cmath>
#include <numeric>
#include <string>
#include <bitset>
#include <assert.h>
#include <iomanip>
using namespace std;

template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// #include <bits/stdc++.h>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// #define getrand(l, r) uniform_int_distribution<int>(l, r)(rng)

const long long infl = 1e18 + 1;
const int inf = 1e9 + 1;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const long double eps = 1e-7;
const int mod = mod2;

int add(int a, int b) { return (a + b) % mod; }
int sub(int a, int b) { return (a - b + mod) % mod; }
int mul(int a, int b) { return (int)((long long)a * b % mod); }
int pwr(int a, int b = mod - 2)
{
  int res = 1;
  for (; b > 0; b >>= 1, a = mul(a, a))
    if (b & 1)
      res = mul(res, a);
  return res;
}
template <typename T>
bool chmax(T &a, T b)
{
  if (b > a)
  {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, T b)
{
  if (b < a)
  {
    a = b;
    return true;
  }
  return false;
}

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define SZ(x) (int)x.size()
#define vec vector
#define dbg(x) cout << (#x) << " : " << x << endl;
using ll = long long;
using ull = unsigned long long;

struct SegmentTree
{
  int n;
  vec<int> a;
  vec<int> seg;
  void build(int l, int r, int v)
  {
    if(l == r)
    {
      seg[v] = a[l];
      return;
    }
    int md = (l + r) / 2;
    build(l, md, v * 2);
    build(md + 1, r, v * 2 + 1);
    seg[v] = seg[v * 2] ^ seg[v * 2 + 1];
  }
  SegmentTree(vec<int> b)
  {
    n = SZ(b);
    a = b;
    seg.resize(n * 4);
    build(1, n, 1);
  }
  void update(int idx, int val, int tl, int tr, int v)
  {
    if(tl == tr)
    {
      seg[v] = val;
      return;
    }
    int md = (tl + tr) / 2;
    if(md >= idx)
    {
      update(idx, val, tl, md, v * 2);
    }
    else
    {
      update(idx, val, md + 1, tr, v * 2 + 1);
    }
    seg[v] = seg[v * 2] ^ seg[v * 2 + 1];
  }
  void update(int idx, int val)
  {
    update(idx, val, 1, n, 1);
  }
  int query(int l, int r, int tl, int tr, int v)
  {
    if(tr < l or r < tl)
    {
      return 0;
    }
    if(l <= tl and tr <= r)
    {
      return seg[v];
    }
    int md = (tl + tr) / 2;
    return query(l, r, tl, md, v * 2) ^ query(l, r, md + 1, tr, v * 2 + 1);
  }
  int query(int l, int r)
  {
    return query(l, r, 1, n, 1);
  }
};

void solve()
{
  int n, q;
  cin >> n >> q;
  vec<int> a(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  vec<int> odd(n + 1), even(n + 1);
  for(int i = 1; i <= n; i++)
  {
    if(i % 2 == 0)
    {
      even[i] = a[i];
    }
    else
    {
      odd[i] = a[i];
    }
  }
  SegmentTree even_st(even), odd_st(odd);
  while (q--)
  {
    int t;
    cin >> t;
    if (t == 1)
    {
      int i, j;
      cin >> i >> j;
      if(i % 2 == 0)
      {
        even_st.update(i, a[i]);
        even_st.update(i, j);
      }
      else
      {
        odd_st.update(i, a[i]);
        odd_st.update(i, j);
      }
      a[i] = j;
    }
    else if (t == 2)
    {
      int l, u;
      cin >> l >> u;

      int len = u - l + 1;
      if (len % 2 == 0)
      {
        cout << 0 << '\n';
        continue;
      }

      int res = 0;
      if (l % 2 == 0)
      {
        res = even_st.query(l, u);
      }
      else
      {
        res = odd_st.query(l, u);
      }
      cout << res << '\n';
    }
  }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  while (t--)
  {
    solve();
    cout << (t ? "\n" : "");
  }
}

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