Submission #459198

# Submission time Handle Problem Language Result Execution time Memory
459198 2021-08-08T10:22:17 Z shmad XORanges (eJOI19_xoranges) C++17
0 / 100
72 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);
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 (tr < pos || tl > pos) {
        return;
    }
    if (tl == tr) {
        t[v][tl & 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][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 = 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:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     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:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     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:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 60 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 72 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -