Submission #747804

#	Time	Username	Problem	Language	Result	Execution time	Memory
747804		Elvin_Fritl	XORanges (eJOI19_xoranges)	C++17	100 / 100	375 ms	11232 KiB

xoranges

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include <bits/stdc++.h>

using namespace std;

vector<int> tree[2];

void build(int in, int v, vector<int> &V, int l, int r) {
    if (l == r) {
        tree[in][v] = V[l];
        return;
    }
    int m = (l + r) / 2;
    build(in, 2 * v, V, l, m);
    build(in, 2 * v + 1, V, m + 1, r);
    tree[in][v] = tree[in][2 * v] ^ tree[in][2 * v + 1];
}

void update(int in, int v, int l, int r, int pos, int val) {
    if (l == r) {
        tree[in][v] = val;
        return;
    }
    int m = (l + r) / 2;
    if (pos <= m) {
        update(in, 2 * v, l, m, pos, val);
    } else {
        update(in, 2 * v + 1, m + 1, r, pos, val);
    }
    tree[in][v] = tree[in][2 * v] ^ tree[in][2 * v + 1];
}

int xor_answer(int in, int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return tree[in][v];
    }
    int m = (l + r) / 2;
    int ll = 0, rr = 0;
    if (ql <= m) {
        ll = xor_answer(in, 2 * v, l, m, ql, qr);
    }
    if (qr > m) {
        rr = xor_answer(in, 2 * v + 1, m + 1, r, ql, qr);
    }
    return ll ^ rr;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, Q;
    cin>>N>>Q;
    vector<int> V(N);
    for(int i=0;i<N;i++) {
        cin>>V[i];
    }
    vector<int> A,B;
    for(int i=0;i<N;i++) {
        if(i%2==0){
            A.push_back(V[i]);
        }
        else{
            B.push_back(V[i]);
        }
    }
    tree[0].resize(4 * A.size());
    tree[1].resize(4 * B.size());
    build(0,1,A,0,A.size()-1);
    build(1,1,B,0,B.size()-1);

    for(int i=0;i<Q;i++) {
        int op,l,r;
        cin>>op>>l>>r;
        l--;
        r--;
        int sz = 0;
        if(l%2==0){
            sz=A.size()-1;
        }
        else{
            sz=B.size()-1;
        }
        if (op==1){
            update(l % 2, 1, 0, sz, l / 2, r + 1);
        }
        else{
            if((r-l+1)%2==0){
                cout<<0<<endl;
                continue;
            }
            cout<<xor_answer(l % 2, 1, 0, sz, l / 2, r / 2)<<endl;
        }
    }
    return 0;
}

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