Submission #791854

#	Time	Username	Problem	Language	Result	Execution time	Memory
791854		Piokemon	XORanges (eJOI19_xoranges)	C++17	100 / 100	102 ms	9476 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

constexpr int base = 262144;
int tree_par[base*2+9];
int tree_nie[base*2+9];

void add_par(int x, int val){
    x += base-1;
    tree_par[x] = val;
    x = x/2;
    while(x>0){
        tree_par[x] = tree_par[2*x] ^ tree_par[2*x+1];
        x = x/2;
    }
}

void add_nie(int x, int val){
    x += base-1;
    tree_nie[x] = val;
    x = x/2;
    while(x>0){
        tree_nie[x] = tree_nie[2*x] ^ tree_nie[2*x+1];
        x = x/2;
    }
}

int query_par(int a, int b, int p, int k, int x){
    if (p<=a && b<=k){
        return tree_par[x];
    }
    if (a>k || b<p){
        return 0;
    }
    int mid = (a+b)/2;
    return query_par(a,mid,p,k,2*x) ^ query_par(mid+1,b,p,k,2*x+1);
}

int query_nie(int a, int b, int p, int k, int x){
    if (p<=a && b<=k){
        return tree_nie[x];
    }
    if (a>k || b<p){
        return 0;
    }
    int mid = (a+b)/2;
    return query_nie(a,mid,p,k,2*x) ^ query_nie(mid+1,b,p,k,2*x+1);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k,t,a,b;
    cin >> n >> k;
    for (int x=1;x<=n;x++){
        cin >> a;
        if (x%2==1){
            add_nie(x,a);
        }
        else{
            add_par(x,a);
        }
    }
    while(k--){
        cin >> t >> a >> b;
        if(t==1){
            if (a%2==1){
                add_nie(a,b);
            }
            else{
                add_par(a,b);
            }
        }
        else{
            if ((b-a+1)%2==0){
                cout << "0\n";
            }
            else{
                if(a%2==1){
                    cout << query_nie(1,base,a,b,1) << "\n";
                }
                else{
                    cout << query_par(1,base,a,b,1) << "\n";
                }
            }
        }
    }
    return 0;
}

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