oj.uz

Submission #430833

# Submission time Handle Problem Language Result Execution time Memory
430833 2021-06-17T06:55:32 Z NintsiChkhaidze XORanges (eJOI19_xoranges) C++14
38 / 100
 210 ms 17676 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 200005;
ll c[N],odd[4*N],even[4*N],a[N];
bool D = 1;
void build(int node,int l,int r){
    if (l == r){
        if (l%2) odd[node] = a[l];
        else even[node] = a[l];
        return;
    }
    build(left),build(right);
    
    odd[node] = odd[(node<<1)]^odd[((node<<1)|1)];
    even[node] = even[(node<<1)]^even[((node<<1)|1)];
}
void upd(int node,int l,int r,int idx,ll val){
    if (l == r){
        if (c[l]) {
            if (l%2) odd[node] = val,even[node] = 0;
            else even[node] = val,odd[node] = 0;
        }
        return;
    }
    if (idx > (l+r)>>1) upd(right,idx,val);
    else upd(left,idx,val);
    
    odd[node] = odd[(node<<1)]^odd[((node<<1)|1)];
    even[node] = even[(node<<1)]^even[((node<<1)|1)];
}
ll get(int node,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) {
        if (D) return odd[node];
        return even[node];
    }
    ll x = get(left,L,R),y = get(right,L,R);
    return x^y;
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n,q;
    cin>>n>>q;
    
    for (int i=1;i<=n;i++)
        cin>>a[i],c[i] = (i*(n - i + 1))%2;
        
    build(1,1,n);
    
    while(q--){
        int tp,x,y;
        cin>>tp>>x>>y;
        if (tp == 1) upd(1,1,n,x,y);
        else {
            D = 1;
            if (!(x%2)) D = 0;
            if ((y-x+1)%2) cout<<get(1,1,n,x,y)<<"\n";
            else cout<<0<<"\n";
        }
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 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 182 ms 12740 KB Output is correct
2 Correct 210 ms 17676 KB Output is correct
3 Correct 188 ms 17600 KB Output is correct
4 Correct 146 ms 17248 KB Output is correct
5 Correct 147 ms 17336 KB Output is correct

Subtask #5
0 / 25.0

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