Submission #911088

#	Time	Username	Problem	Language	Result	Execution time	Memory
911088		speedcode	XORanges (eJOI19_xoranges)	C++17	100 / 100	128 ms	8028 KiB

xoranges

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

int biggestPowOf2(int i){
    int res = 1;
    while(i % 2 == 0){
        res *= 2;
        i /= 2;
    }
    return res;
}

void xorToArray(long long* arr, int index, long long value, int arrLength){
    while(index < arrLength){
        arr[index] ^= value;
        index += biggestPowOf2(index);
    }
}

int ArraySum(long long* arr, int index){
    if(index == 0) return 0;
    return arr[index] ^ ArraySum(arr, index - biggestPowOf2(index));
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    long long oddValues[(n+1)/2 + 1];
    int oddLength = (n+1)/2 + 1;
    long long evenValues[n/2 + 1];
    int evenLength = n/2 + 1;
    fill(oddValues,oddValues + oddLength, 0);
    fill(evenValues,evenValues + evenLength, 0);
    for(int i = 1; i <= n; i++){
        long long r;
        cin >> r;
        if(i%2 == 0){
            xorToArray(evenValues, i/2, r, evenLength);
        } else {
            xorToArray(oddValues, i/2 + 1, r, oddLength);
        }
    }
    for(int i = 0; i < q; i++){
        short int t;
        cin >> t;
        if(t==2){
            int l,u;
            cin >> l >> u;
            if((l-u)%2 != 0){
                cout << "0\n";
            } else if(l%2 == 0){
                cout << (ArraySum(evenValues, u/2) ^ ArraySum(evenValues, l/2 - 1)) << '\n';
            } else {
                cout << (ArraySum(oddValues, u/2 + 1) ^ ArraySum(oddValues, l/2)) << '\n';
            }

        } else {
            int I;
            long long val;
            cin >> I;
            cin >> val;
            if(I%2 == 0){
                xorToArray(evenValues, I/2, (ArraySum(evenValues, I/2) ^ ArraySum(evenValues, I/2 - 1) ^ val), evenLength);
            } else {
                xorToArray(oddValues, I/2 + 1, (ArraySum(oddValues, I/2 + 1) ^ ArraySum(oddValues, I/2) ^ val), oddLength);
            }
        }
    }
}

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