Submission #675717

#	Time	Username	Problem	Language	Result	Execution time	Memory
675717		a_aguilo	XORanges (eJOI19_xoranges)	C++14	100 / 100	598 ms	9720 KiB

xoranges

#include<bits/stdc++.h>

using namespace std;

vector<int> segTreeOdd, segTreeEven, Odds, Evens;
int n, q;

void setUpSegTree(int node, int left, int right, vector<int>& refVector, vector<int>& SegTree){
    if(left == right) {
        SegTree[node] = refVector[left];
        return;
    }
    if(left > right) return;
    int mid = left + (right - left)/2;
    setUpSegTree(2*node, left, mid, refVector, SegTree);
    setUpSegTree(2*node+1, mid+1, right, refVector, SegTree);
    SegTree[node] = SegTree[2*node]^SegTree[2*node+1];
}

void update(int node, int left, int right, int position, int newVal, vector<int>& SegTree){
    if(right < position || left > position) return;
    if(right < left) return;
    //cout << "Node " << node << " leftBound " << left << " rightBound " << right << endl;
    if(right == left){
        SegTree[node] = newVal;
        return;
    }
    int mid = left + (right - left)/2;
    update(2*node, left, mid, position, newVal, SegTree);
    update(2*node+1, mid+1, right, position, newVal, SegTree);
    SegTree[node] = SegTree[2*node]^SegTree[2*node+1];
    //cout << "Node " << node << " leftBound " << left << " rightBound " << right << " segtree val " << SegTree[node] <<  endl;
}

int getValue(int node, int left, int right, int leftBound, int rightBound, vector<int>& SegTree){
    //cout << node << " " << left << " " << right << " " << leftBound << " " << rightBound << endl;
    if(left > rightBound || right < leftBound) return 0;
    if(left > right) return 0;
    if(leftBound <= left && rightBound >= right) return SegTree[node];
    int mid = left + (right - left)/2;
    return (getValue(2*node, left, mid, leftBound, rightBound, SegTree)^getValue(2*node+1, mid+1, right, leftBound, rightBound, SegTree));
}
int main(){
    cin >> n >> q;
    int ask, l, r, pos, newVal, concretePos;
    vector<int> indices(n);
    for(int i = 0; i < n; ++i){
        cin >> indices[i];
        if(i%2){//índice IMPAR
            Odds.push_back(indices[i]);
        }else{
            Evens.push_back(indices[i]);
        }
    }
    segTreeOdd = vector<int>(4*Odds.size());
    setUpSegTree(1, 0, Odds.size()-1, Odds, segTreeOdd);
    segTreeEven = vector<int>(4*Evens.size());
    setUpSegTree(1, 0, Evens.size()-1, Evens, segTreeEven);
    while(q--){
        cin >> ask;
        if(ask == 1){
            cin >> pos >> newVal;
            pos--;
            if(pos%2){
                update(1, 0, Odds.size()-1, pos/2, newVal, segTreeOdd);
            }else{
                update(1, 0, Evens.size()-1, pos/2, newVal, segTreeEven);
            }
        }else{
            cin >> l >> r;l--; r--;
            if((l-r+1)%2){
                if(l%2== 0){
                    cout << getValue(1, 0, Evens.size()-1, l/2, r/2, segTreeEven)<< endl;
                }
                else{
                    cout << getValue(1, 0, Odds.size()-1, l/2, r/2, segTreeOdd) << endl;
                }
            }else{
                cout << 0 << endl;
            }
        }
    }
    return 0;
}

Compilation message (stderr)

xoranges.cpp: In function 'int main()':
xoranges.cpp:45:33: warning: unused variable 'concretePos' [-Wunused-variable]
   45 |     int ask, l, r, pos, newVal, concretePos;
      |                                 ^~~~~~~~~~~

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