oj.uz

Submission #237583

# Submission time Handle Problem Language Result Execution time Memory
237583 2020-06-07T14:19:37 Z tb_03 XORanges (eJOI19_xoranges) C++14
0 / 100
 742 ms 5624 KB 
#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 - 1];

      if (index - 1 % 2 == 0)
        update_par(index - 1);
      else
        update_impar(index - 1);
    }
    else
    {
      //query
      int l, u;
      cin >> l >> u;

      if ((u - l + 1) % 2 == 0)
        cout << 0 << '\n';
      else if (l - 1 % 2 == 0)
        cout << query_par(l - 1, u - 1) << '\n';
      else
        cout << query_impar(l - 1, u - 1) << '\n';
    }
  }

  cout.flush();
  return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 742 ms 5624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -