Submission #459216

#	Time	Username	Problem	Language	Result	Execution time	Memory
459216		shmad	XORanges (eJOI19_xoranges)	C++14	100 / 100	177 ms	20420 KiB

xoranges

#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 = 2e5 + 5;
const int INF = 1e18 + 7;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const int B = 800;

vt<int> a(N), t(4 * N), t1(4 * N);
int n;

void build (int v = 1, int tl = 1, int tr = n) {
    if (tl == tr) {
        if (tl & 1) t1[v] = a[tl];
        else t[v] = a[tl];
        return;
    }
    int tm = tl + tr >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
    t[v] = (t[v << 1] ^ t[v << 1 | 1]);
    t1[v] = (t1[v << 1] ^ t1[v << 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) {
        if (pos & 1) t1[v] = val;
        else t[v] = 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] = (t[v << 1] ^ t[v << 1 | 1]);
    t1[v] = (t1[v << 1] ^ t1[v << 1 | 1]);
}

int get (int l, int r, int v = 1, int tl = 1, int tr = n) {
    if (tl > r || tr < l) {
        return 0;
    }
    if (tl >= l && tr <= r) {
        if (l & 1) return t1[v];
        else return t[v];
    }
    int tm = tl + tr >> 1;
    int a = get(l, r, v << 1, tl, tm);
    int b = get(l, r, 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) << 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 (stderr)

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:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     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)':
xoranges.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25