oj.uz

Submission #459223

# Submission time Handle Problem Language Result Execution time Memory
459223 2021-08-08T10:50:42 Z shmad XORanges (eJOI19_xoranges) C++14
0 / 100
 65 ms 65540 KB 
#include <bits/stdc++.h>

#define nl '\n'
#define pb push_back
#define E exit(0)
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define sz(s) (int)(s).size()
#define ll long long
#define int ll
#define oioi ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define vt vector

using namespace std;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;

const int N = 1e6 + 1;
const int INF = 1e18 + 7;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const int B = 800;

vt<int> a(N);
int n;
vvi t(4 * N, vt<int> (2, 0));

void build (int v = 1, int tl = 1, int tr = n) {
  if (tl == tr) {
    t[v][tl & 1] = a[tl];
    return;
  }
  int tm = tl + tr >> 1;
  build(v << 1, tl, tm);
  build(v << 1 | 1, tm + 1, tr);
  t[v][0] = (t[v << 1][0] ^ t[v << 1 | 1][0]);
  t[v][1] = (t[v << 1][1] ^ t[v << 1 | 1][1]);
}

void upd (int pos, int val, int v = 1, int tl = 1, int tr = n) {
  if (tl > pos || tr < pos) {
    return;
  }
  if (tl == tr && tl == pos) {
    t[v][pos & 1] = val;
    return;
  }
  int tm = tl + tr >> 1;
  upd(pos, val, v << 1, tl, tm);
  upd(pos, val, v << 1 | 1, tm + 1, tr);
  t[v][pos & 1] = (t[v << 1][pos & 1] ^ t[v << 1 | 1][pos & 1]);
}

int get (int l, int r, int check, int v = 1, int tl = 1, int tr = n) {
  if (tl > r || tr < l) {
    return 0;
  }
  if (tl >= l && tr <= r) {
    return t[v][check];
  }
  int tm = tl + tr >> 1;
  int a = get(l, r, check, v << 1, tl, tm);
  int b = get(l, r, check, v << 1 | 1, tm + 1, tr);
  return (a ^ b);
}

void solve () {
  int q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build();
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int pos, x;
      cin >> pos >> x;
      upd(pos, x);
    }
    if (type == 2) {
      int l, r;
      cin >> l >> r;
      if ((r - l + 1) & 1) cout << get(l, r, (l & 1)) << nl;
      else cout << "0\n";
    }
  }
  cout << nl;
}

int test = 1;

signed main () {
  //	freopen(".in", "r", stdin);
  //	freopen(".out", "w", stdout);
  oioi
    //	cin >> test; 
    while (test--) solve();
  return 0;
}

Compilation message

xoranges.cpp: In function 'void build(long long int, long long int, long long int)':
xoranges.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
xoranges.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
xoranges.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
xoranges.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int, long long int)':
xoranges.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   int tm = tl + tr >> 1;
      |            ~~~^~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -