oj.uz

Submission #1021309

# Submission time Handle Problem Language Result Execution time Memory
1021309 2024-07-12T16:49:42 Z mar XORanges (eJOI19_xoranges) C++14
100 / 100
 406 ms 11376 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int seg1[600009];
int seg2[600009];
int v[600009];
 
void build(int id,int l,int r){
    if(l == r){
        if(l % 2 == 1){
            return;
        }
        seg1[id] = v[l];
        return;
    }
    int mid = (l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    seg1[id] = seg1[id*2]^seg1[id*2+1];
}
 
void update(int l,int r,int u,int v,int k){
    if(l == r && l == v){
        seg1[u] = k;
        return;
    }
    if(v < l || v > r)return;
    int mid = (l+r)/2;
    update(l,mid,u*2,v,k);
    update(mid+1,r,u*2+1,v,k);
    seg1[u] = seg1[u*2]^seg1[u*2+1];
}
 
int query(int id,int l,int r,int a,int b,int res){
    if(a <= l && b >= r){
        return seg1[id]^res;
    }
    if(l > b || r < a){
        return res;
    }
    int mid = (l+r)/2;
    res = query(id*2,l,mid,a,b,res);
    res = query(id*2+1,mid+1,r,a,b,res);
    return res;
}
 
void build2(int id,int l,int r){
    if(l == r){
        if(l % 2 == 0){
            return;
        }
        seg2[id] = v[l];
        return;
    }
    int mid = (l+r)/2;
    build2(id*2,l,mid);
    build2(id*2+1,mid+1,r);
    seg2[id] = seg2[id*2]^seg2[id*2+1];
}
 
void update2(int l,int r,int u,int v,int k){
    if(l == r && l == v){
        seg2[u] = k;
        return;
    }
    if(v < l || v > r)return;
    ll mid=(l+r)/2;
    update2(l,mid,u*2,v,k);
    update2(mid+1,r,u*2+1,v,k);
    seg2[u] = seg2[u*2]^seg2[u*2+1];
}
 
 
int query2(int id,int l,int r,int a,int b,int res){
    if(a <= l && b >= r){
        return seg2[id]^res;
    }
    if(l > b || r < a){
        return res;
    }
    ll mid = (l+r)/2;
    res = query2(id*2,l,mid,a,b,res);
    res = query2(id*2+1,mid+1,r,a,b,res);
    return res;
}
 
int main() {
    int n,q;
    cin >> n >> q;
    for(int i = 0;i < n;i++){
        cin >> v[i];
    }
    build(1,0,n-1);
    build2(1,0,n-1);
    while(q--){
        int x,l,r;
        cin >> x >> l >> r;
        if(x == 1){
            l--;
            if(l % 2 == 0){
                update(0,n-1,1,l,r);
            }else{
                update2(0,n-1,1,l,r);
            }
        }else{
            l--;
            r--;
            if((r-l)%2 == 1){
                cout<<0<<endl;
            }else{
                if(l%2 == 0){
                    cout<<query(1,0,n-1,l,r,0)<<endl;
                }else{
                    cout<<query2(1,0,n-1,l,r,0)<<endl;
                }
            }
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 12 ms 604 KB Output is correct
12 Correct 8 ms 732 KB Output is correct
13 Correct 9 ms 600 KB Output is correct
14 Correct 9 ms 604 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 11288 KB Output is correct
2 Correct 387 ms 11348 KB Output is correct
3 Correct 393 ms 11376 KB Output is correct
4 Correct 363 ms 10832 KB Output is correct
5 Correct 406 ms 10968 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 12 ms 604 KB Output is correct
12 Correct 8 ms 732 KB Output is correct
13 Correct 9 ms 600 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 381 ms 11288 KB Output is correct
16 Correct 387 ms 11348 KB Output is correct
17 Correct 393 ms 11376 KB Output is correct
18 Correct 363 ms 10832 KB Output is correct
19 Correct 406 ms 10968 KB Output is correct
20 Correct 292 ms 11092 KB Output is correct
21 Correct 323 ms 11008 KB Output is correct
22 Correct 286 ms 10832 KB Output is correct
23 Correct 390 ms 10836 KB Output is correct
24 Correct 373 ms 10836 KB Output is correct