oj.uz

Submission #815706

# Submission time Handle Problem Language Result Execution time Memory
815706 2023-08-08T19:24:33 Z AndrijaM XORanges (eJOI19_xoranges) C++14
100 / 100
 451 ms 14664 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;
            if((r - l + 1 ) % 2 == 0) {
                cout << 0 <<endl;
                continue;
            }
            l--,r--;
            if(l%2 == 0){
                cout << st1.query(l,r) << endl;
            }
            else {
                cout << st2.query(l, r) << endl;
            }
        }
    }

}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 3 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 11 ms 468 KB Output is correct
12 Correct 9 ms 544 KB Output is correct
13 Correct 10 ms 468 KB Output is correct
14 Correct 10 ms 468 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 10036 KB Output is correct
2 Correct 429 ms 10080 KB Output is correct
3 Correct 406 ms 10076 KB Output is correct
4 Correct 451 ms 10108 KB Output is correct
5 Correct 403 ms 10116 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 3 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 11 ms 468 KB Output is correct
12 Correct 9 ms 544 KB Output is correct
13 Correct 10 ms 468 KB Output is correct
14 Correct 10 ms 468 KB Output is correct
15 Correct 422 ms 10036 KB Output is correct
16 Correct 429 ms 10080 KB Output is correct
17 Correct 406 ms 10076 KB Output is correct
18 Correct 451 ms 10108 KB Output is correct
19 Correct 403 ms 10116 KB Output is correct
20 Correct 355 ms 9496 KB Output is correct
21 Correct 371 ms 14664 KB Output is correct
22 Correct 320 ms 14632 KB Output is correct
23 Correct 395 ms 14508 KB Output is correct
24 Correct 399 ms 14544 KB Output is correct