Submission #637397

#	Time	Username	Problem	Language	Result	Execution time	Memory
637397		kideso	XORanges (eJOI19_xoranges)	C++17	100 / 100	565 ms	5588 KiB

xoranges

#include <iostream>
#include <queue>

using namespace std;

vector<vector<int> > x;
int N, Q;

struct Segment_tree{
    vector<int> st;

    void init_segment_tree(int N){
        st.assign(4 * N + 1, 0);
    }

    void build_segment_tree(int p, int l, int r, int k){
        if(l == r){
            st[p] = x[k][l];
            return;
        }

        int m = (l + r) / 2;
        build_segment_tree(2 * p, l, m, k);
        build_segment_tree(2 * p + 1, m + 1, r, k);

        st[p] = st[2 * p] ^ st[2 * p + 1];
    }

    void update_segment_tree(int p, int l, int r, int k, int i){
        if(l == r){
            st[p] = x[k][l];
            return;
        }

        int m = (l + r) / 2;
        if(i <= m)
            update_segment_tree(2 * p, l, m, k, i);
        else
            update_segment_tree(2 * p + 1, m + 1, r, k, i);

        st[p] = st[2 * p] ^ st[2 * p + 1];
    }

    int range_query(int p, int l, int r, int ql, int qr){
        if(ql <= l && r <= qr)
            return st[p];
        
        if(r < ql || qr < l) return 0;

        int m = (r + l) / 2;
        
        return range_query(2 * p, l, m, ql, qr) ^ range_query(2 * p + 1, m + 1, r, ql, qr);
    }
};

int main(){
    cin >> N >> Q;

    x.assign(2, vector<int> ());

    x[0].push_back(0);
    x[1].push_back(0);
    int p;

    for(int i = 1; i <= N; ++i){
        cin >> p;
        x[i % 2].push_back(p);
    }

    Segment_tree stree[2];

    for(int i = 0; i < 2; ++i){
        stree[i].init_segment_tree(x[i].size());
        stree[i].build_segment_tree(1, 1, x[i].size() - 1, i);
    }

    int t, a, b;

    while(Q--){
        cin >> t >> a >> b;
        if(t == 1){
            x[a % 2][a / 2 + a % 2] = b;
            stree[a % 2].update_segment_tree(1, 1, x[a % 2].size() - 1, a % 2, a / 2 + a % 2);
        }
        else{
            if((b - a + 1) % 2 == 0){
                cout << 0 << '\n';
                continue;
            }
            else
                cout << stree[a % 2].range_query(1, 1, x[a % 2].size() - 1, a / 2 + a % 2, b / 2 + b % 2) << '\n';
        }
    }

    return 0;
}

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