Submission #237581

#	Time	Username	Problem	Language	Result	Execution time	Memory
237581		tb_03	XORanges (eJOI19_xoranges)	C++14	0 / 100	740 ms	5624 KiB

xoranges

#include <iostream>

using namespace std;
typedef unsigned int ui;
 
int n, q;
ui oranges[200005];
ui st_par[400005];
ui st_impar[400005];
 
void update_par(int index)
{
  st_par[n + index] = oranges[index];
 
  for (int i = n + index; i > 1; i >>= 1)
    st_par[i >> 1] = st_par[i] ^ st_par[i ^ 1];
}
 
void update_impar(int index)
{
  st_impar[n + index] = oranges[index];
 
  for (int i = n + index; i > 1; i >>= 1)
    st_impar[i >> 1] = st_impar[i] ^ st_impar[i ^ 1];
}
 
ui query_par(int l, int r)
{
  ui res = 0;
 
  for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
  {
    if (l & 1)
      res ^= st_par[l++];
 
    if (r & 1)
      res ^= st_par[--r];
  }
 
  return res;
}
 
ui query_impar(int l, int r)
{
  ui res = 0;
 
  for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
  {
    if (l & 1)
      res ^= st_impar[l++];
 
    if (r & 1)
      res ^= st_impar[--r];
  }
 
  return res;
}
 
int main()
{
  cin >> n >> q;
 
  for (int i = 0; i < n; i++)
    cin >> oranges[i];
 
  for (int i = 0; i < n; i++)
    st_par[n + i] = (i % 2 == 0 ? oranges[i] : 0);
 
  for (int i = n - 1; i > 0; i--)
    st_par[i] = st_par[i << 1] ^ st_par[i << 1 | 1];
 
  for (int i = 0; i < n; i++)
    st_impar[n + i] = (i % 2 == 0 ? 0 : oranges[i]);
 
  for (int i = n - 1; i > 0; i--)
    st_impar[i] = st_impar[i << 1] ^ st_impar[i << 1 | 1];
 
  while (q--)
  {
    int aux;
    cin >> aux;
 
    if (aux == 1)
    {
      //rescan
      int index;
      cin >> index;
      cin >> oranges[index];
 
      if (index % 2 == 0)
        update_par(index);
      else
        update_impar(index);
    }
    else
    {
      //query
      int l, u;
      cin >> l >> u;
 
      if ((u - l + 1) % 2 == 0)
        cout << 0 << '\n';
      else if (l % 2 == 0)
        cout << query_par(l, u) << '\n';
      else
        cout << query_impar(l, u) << '\n';
    }
  }
 
  cout.flush();
  return 0;
}

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