oj.uz

Submission #1099560

# Submission time Handle Problem Language Result Execution time Memory
1099560 2024-10-11T16:09:06 Z vjudge1 XORanges (eJOI19_xoranges) C++17
0 / 100
 513 ms 17068 KB 
#include <bits/stdc++.h>
using namespace std;

string abc = "abcdefghijklmnopqrstuvwxyz";

#define int long long


const int N = 2e5+7;

struct segTree{
    int sz;
    vector<int> t, a;
    void init(int n){
        sz = 1;
        while(sz < n) sz*=2;
        t.assign(2*sz, 0);
    }

    void merge(int v){
        t[v]=t[2*v]^t[2*v+1];
    }

    void inn(int v, int tl, int tr){
        if(tl == tr){
            t[v] = a[tl-1];
            return;
        }
        int tm = (tl+tr)/2;
        inn(2*v, tl, tm);
        inn(2*v+1, tm+1, tr);
        merge(v);
    }

    void in(int n, vector<int> va){
        a = va;
        inn(1, 1, n);
        for(int i = 1; i <= n; i++){
        }
    }

    int get(int v, int tl, int tr, int l, int r){
        // if(min(v, tl) < 0) return 33;
        if(tl == l && tr == r){
            return t[v];
        }
        int tm = (tl+tr)/2;
        if(tm >= r) return get(2*v, tl, tm, l, r);
        if(tm < l) return get(2*v+1, tm+1, tr, l, r);
        int ga = get(2*v, tl, tm, l, tm), gb = get(2*v+1, tm+1, tr, tm+1, r);
        return ga^gb;
    }

    void upd(int v, int tl, int tr, int pos, int va){
        if(tl == tr){
            t[v]=va;
            return;
        }
        int tm = (tl+tr)/2;
        if(tm >= pos) upd(2*v, tl, tm, pos, va);
        else upd(2*v+1, tm+1, tr, pos, va);
        merge(v);
    }

};



signed  main(){
    int n, q;
    cin >> n >> q;
    vector<int> v(n+1);
    for(int i = 1; i <= n; i++) cin >> v[i];
    segTree sa, sb;
    sa.init(n/2+2);
    sb.init(n/2+2);
    vector<int> ra, rb;
    for(int i = 1; i <= n; i++){
        if(i%2 == 1){
            ra.push_back(v[i]);
        }
        else rb.push_back(v[i]);
    }

    sa.in(ra.size(), ra);
    sb.in(rb.size(), rb);
    int na = ra.size();
    int nb = rb.size();
     n = n/2+2;
    while(q--){
        int qu;
        cin >> qu;
        if(qu == 1){
            int p, va;
            cin >> p >> va;
            if(p%2 == 0){
                int np = p/2;
                sb.upd(1, 1, nb, np, va);
            }
            else{
                int np = p/2+1;
                sa.upd(1, 1, na, np, va);
            }
        }
        else{
            int l, r;
            cin >> l >> r;
            if((r-l+1)%2 == 0){
                cout << 0 << endl;
            }
            if(l%2 == 0){
                int ll = l/2, rr = r/2;
                int ans = sb.get(1, 1, nb, ll, rr);
                cout << ans << endl;
            }
            else{
                int ll = (l+1)/2, rr = (r+1)/2;
                int ans = sa.get(1, 1, na, ll, rr);
                cout << ans << endl;
            }
        }
    }
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 513 ms 17068 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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -