oj.uz

Submission #725668

# Submission time Handle Problem Language Result Execution time Memory
725668 2023-04-17T20:37:27 Z MercubytheFirst XORanges (eJOI19_xoranges) C++14
38 / 100
 504 ms 10476 KB 
#include<iostream>
#include<vector>
using namespace std;


#define R (node * 2 + 1)
#define L (node * 2)
#define CDIV(a, b) (((a) + (b) - 1) / (b))
class ST{
    public:
    int n;
    vector<int>t, v;

    ST(int sz){
        n = sz;
        t.resize(4 * n);
        v.resize(n + 1);
    }

    void build(int node, int l, int r){
        if(l == r){
            t[node] = v[l];
            return;
        }
        int mid = (l + r)/2;
        build(L, l, mid);
        build(R, mid + 1, r);
        t[node] = t[L] ^ t[R];
    }

    int query(int node, int l, int r, int tl, int tr){
        if(l > r or r < tl or tr < l)return 0;
        if(tl <= l and r <= tr){
            return t[node];
        }
        int mid = (l + r)/2;
        int res = query(L,l, mid, tl, tr) ^ query(R, mid + 1, r, tl, tr);
        return res;
    }

    void update(int node, int l, int r, int idx, int val){
        if(l > r or r < idx or idx < l)return;
        if(l == r){
            t[node] = val;
            return;
        }
        int mid = (l + r)/2;
        update(L, l, mid, idx, val);
        update(R, mid + 1, r, idx, val);
        t[node] = t[R] ^ t[L];
    }

};


int main(){
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    int n, q;
    cin >> n >> q;
    int esz = n/2, osz = CDIV(n,2);
    ST even(esz), odd(osz);
    for(int i = 1; i <= n; ++i){
        if(i % 2){
            cin >> odd.v[i/2 + 1];
        }
        else cin >> even.v[i/2];
    }
    even.build(1, 1,esz);
    odd.build(1, 1, osz);

    while(q--){
        int qt;
        cin >> qt;
        if(qt == 1){
            int idx, val;
            cin >> idx >> val;
            if(idx % 2){
                odd.update(1, 1, osz, idx, val);
            }
            else{
                even.update(1, 1, esz, idx, val);
            }
        }
        else{
            int l, r;
            cin >> l >> r;
            if((r - l + 1) % 2 == 0){
                cout << 0 << endl;
                continue;
            }
            if(l & 1){
                cout << odd.query(1, 1, osz, l/2 + 1, r/2 + 1) << endl;
            }
            else{
                cout << even.query(1, 1, esz, l/2, r/2) << 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
18.0 / 18.0

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

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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 10332 KB Output is correct
2 Correct 499 ms 10476 KB Output is correct
3 Correct 499 ms 10236 KB Output is correct
4 Correct 470 ms 9920 KB Output is correct
5 Correct 466 ms 9976 KB Output is correct

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 -