oj.uz

Submission #815704

# Submission time Handle Problem Language Result Execution time Memory
815704 2023-08-08T19:19:49 Z AndrijaM XORanges (eJOI19_xoranges) C++14
0 / 100
 460 ms 10980 KB 
#include<bits/stdc++.h>
#include<math.h>

#define _USE_MATH_DEFINES

using namespace std;

struct segTree {
    vector<int> seg;
    int n;
    void build(int s, int e, int curr, vector<int>& v) {
        if (s == e) {
            seg[curr] = v[s];
            return;
        }
        int mid = (s + e) / 2;

        build(s, mid, curr * 2 + 1, v);
        build(mid + 1, e, curr * 2 + 2, v);

        seg[curr] = seg[curr * 2 + 1] ^ seg[curr * 2 + 2];
    }

    void build(vector<int> &v){
        build(0, n - 1, 0, v);
    }

    segTree(vector<int> v) {
        n = v.size();
        seg.resize(4 * n, 0); // 2 * pow(2, log2(n)) - 1;
        build(v);
    }

    int query(int s, int e, int curr, int rS, int rE){
        if(e < rS || s > rE) return 0;
        else if(s >= rS && e <=rE){
            return seg[curr];
        }
        else {
            int mid = (s + e) / 2;
            int q1 = query(s, mid, curr * 2 + 1, rS, rE);
            int q2 = query(mid + 1, e, curr * 2 + 2, rS, rE);

            return q1 ^ q2;

        }
    }

    int query(int rS, int rE){
        return query(0, n-1, 0, rS, rE);
    }

    void update(int s, int e, int curr, int index, int val){
        if(s == e) {
            seg[curr] = val;
            return;
        }
        int mid = (s + e) / 2;
        if(index <= mid){
            update(s, mid, curr * 2 + 1, index, val);
        }
        else{
            update(mid + 1, e, curr * 2 + 2, index, val);
        }

        seg[curr] = seg[curr * 2 + 1] ^ seg[curr * 2 + 2];

    }

    void update(int index, int val){
        update(0, n-1, 0, index, val);
    }
};


int main()
{
    int n, q;
    cin>>n>>q;
    vector<int> neparni;
    vector<int> parni;
    for(int i = 0; i<n; i++){
        int x;
        cin>>x;
        if(i%2 == 0){
            neparni.push_back(x);
            parni.push_back(0);
        }
        else{
            parni.push_back(x);
            neparni.push_back(0);
        }
    }
    segTree st1(neparni);
    segTree st2(parni);

    while(q--){
        int t;
        cin>>t;
        if(t == 1){
            int ind, val;
            cin>>ind>>val;
            ind--;
            if(ind % 2 == 0){
                st1.update(ind,val);
            }
            else st2.update(ind, val);
        }
        else{
            int l, r;
            cin>>l>>r;
            l--,r--;
            if(l%2 == 0){
                cout << st1.query(l,r) << endl;
            }
            else {
                cout << st2.query(l, r) << endl;
            }
        }
    }

}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 460 ms 10980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -