oj.uz

Submission #459201

# Submission time Handle Problem Language Result Execution time Memory
459201 2021-08-08T10:24:53 Z shmad XORanges (eJOI19_xoranges) C++14
0 / 100
 68 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 + 5;
const int INF = 1e18 + 7;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const int B = 800;

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

void build (int v, int tl, int tr) {
    if(tl == tr) {
        t[v][tl % 2] = 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, int tl, int tr) {
    if (tr < pos || tl > pos) {
        return;
    }
    if (tl == tr) {
        t[v][tl % 2] = 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][0] = (t[v << 1][0] ^ t[v << 1 | 1][0]);
    t[v][1] = (t[v << 1][1] ^ t[v << 1 | 1][1]);
}

int get (int l, int r, int check, int v, int tl, int tr) {
    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 n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, x;
            cin >> pos >> x;
            upd(pos, x, 1, 1, n);
        }
        if (type == 2) {
            int l, r;
            cin >> l >> r;
            if ((r - l + 1) % 2 == 1) cout << get(l, r, (l % 2), 1, 1, n) << 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:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     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:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     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:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 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 60 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 68 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 56 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 68 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -