oj.uz

Submission #237581

# Submission time Handle Problem Language Result Execution time Memory
237581 2020-06-07T14:07:00 Z tb_03 XORanges (eJOI19_xoranges) C++14
0 / 100
 740 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];
 
      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.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 740 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 -