Submission #563516

#	Time	Username	Problem	Language	Result	Execution time	Memory
563516		beep_boop	XORanges (eJOI19_xoranges)	C++17	100 / 100	163 ms	11260 KiB

xoranges

/*
 * Created at 4:36 PM on 17 May, 2022
 */

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <numeric>
#include <cassert>
#include <functional>
using namespace std;
 
#define rep(i,a,b) for(auto (i)=a;(i)<(b);(i)++)
#define list(i,N) for(auto (i)=0;(i)<(N);(i)++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SZ(x) (int)(x).size()
#define vt vector
#define trav(a, x) for(auto& (a): (x))
#define DO if(true)

#define mp make_pair
#define pb push_back
#define eb emplace_back

//#define int int64_t

typedef vector<int> vi;
typedef pair<int, int> pi;

#define mod 1000000007
 
void setIO(){
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
}

template <typename T>
void read(vector<T> &a, int n) {
    a.resize(n);
    for (auto &x: a) cin >> x;
}

template<class T, class U>
ostream& operator <<(ostream& out, const pair<T,U> &v){
    out << "(";
    out << v.first << ", " << v.second;
    return out << ")";
}

template<class T>
ostream& operator <<(ostream& out, const vector<T> &v) {
    out << "[";
    list(i, SZ(v)) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

template <typename T>
void print(vector<T> &a) {
    for (const auto& x: a) cout << x << ' ';
    cout << '\n';
}

template<typename T>
void MOD(T& x, int m = mod){
    x %= m;
    if(x < 0) x += m;
}

#define trace(...) dbg(#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void dbg(const char* name, T&& arg1){
    cout << name << " : " << arg1 << '\n';
}
template <typename T, typename... U>
void dbg(const char* names, T&& arg1, U&&... args){
    const char* comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | ";
    dbg(comma+1, args...);
}

template<class T> void read(T& x) {
    cin >> x;
}

template<class T, class... U> void read(T& t, U&... u) {
    read(t);
    read(u...);
}

int gcd(int a, int b) { return !a ? b : gcd(b%a,a); }
int ceil_div(int a, int b) { return (a + b - 1) / b; }

using ll = int64_t;

/*
 * Range Xor
 * Point Update
 */
struct SegTree {
    int size = 1;
    vi elements;

    void init(int n){
        while(size < n){
            size *= 2;
        }

        elements.assign(2 * size, 0);
    }

    void pull(int x){
        elements[x] = elements[2 * x + 1] ^ elements[2 * x + 2];
    }

    void set(int i, int v, int x, int lx, int rx){
        if(rx - lx == 1){
            elements[x] = v;
            return;
        }

        int mid = (lx + rx) / 2;

        if(i < mid){
            set(i, v, 2 * x + 1, lx, mid);
        }else {
            set(i, v, 2 * x + 2, mid, rx);
        }

        pull(x);
    }

    void set(int i, int v){
        set(i, v, 0, 0, size);
    }

    int calc(int l, int r, int x, int lx, int rx){
        if(l >= rx or r <= lx){
            return 0;
        }
        if(l <= lx and rx <= r){
            return elements[x];
        }

        int mid = (lx + rx) / 2;
        int r1 = calc(l, r, 2 * x + 1, lx, mid);
        int r2 = calc(l, r, 2 * x + 2, mid, rx);
        int ans = r1 ^ r2;

        return ans;
    }

    int calc(int l, int r){
        return calc(l, r, 0, 0, size);
    }
};

const int N = int(2e5) + 10;
int n, q;
vi a;

int32_t main(){
    setIO();

    read(n, q);
    read(a, n);

    SegTree st[2];
    list(i, 2){
        st[i].init(n);
    }
    list(i, n){
        st[i & 1].set(i, a[i]);
    }

    int op, idx, l, r, v;
    while(q--){
        read(op);

        if(op == 1){
            read(idx);
            read(v);
            idx--;

            st[idx & 1].set(idx, v);
        }else {
            read(l, r);
            l--;

            if ((r - l) % 2 == 0) {
                cout << "0\n";
                continue;
            }

            cout << st[l & 1].calc(l, r) << '\n';
        }
    }

	return 0;
}

Compilation message (stderr)

xoranges.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<T>&)':
xoranges.cpp:22:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   22 | #define list(i,N) for(auto (i)=0;(i)<(N);(i)++)
      |                            ^
xoranges.cpp:62:5: note: in expansion of macro 'list'
   62 |     list(i, SZ(v)) {
      |     ^~~~
xoranges.cpp: In function 'int32_t main()':
xoranges.cpp:22:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   22 | #define list(i,N) for(auto (i)=0;(i)<(N);(i)++)
      |                            ^
xoranges.cpp:180:5: note: in expansion of macro 'list'
  180 |     list(i, 2){
      |     ^~~~
xoranges.cpp:22:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   22 | #define list(i,N) for(auto (i)=0;(i)<(N);(i)++)
      |                            ^
xoranges.cpp:183:5: note: in expansion of macro 'list'
  183 |     list(i, n){
      |     ^~~~

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