oj.uz

Submission #819838

# Submission time Handle Problem Language Result Execution time Memory
819838 2023-08-10T14:05:54 Z Andrijanikolic73 XORanges (eJOI19_xoranges) C++17
75 / 100
 124 ms 17688 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define int long long
using namespace std;
const int N=2e5+50;
const int inf=1e18;
const int mod=1e9+7;
int a[N];
int n;
int q;
int A[N];
struct segtree{
    int t[4*N]={0};
    void build(int v,int tl,int tr){
        if(tl==tr)t[v]=A[tl];
        else {
            int tm=(tl+tr)/2;
            build(v*2,tl,tm);
            build(v*2+1,tm+1,tr);
            t[v]=(t[v*2]^t[v*2+1]);
        }
    }
    int query(int v,int tl,int tr,int l,int r){
        if(tr<l||tl>r)return 0;
        if(l<=tl&&tr<=r)return t[v];
        int tm=(tl+tr)/2;
        return (query(v*2,tl,tm,l,r)^query(v*2+1,tm+1,tr,l,r));
    }
    void update(int v,int tl,int tr,int index,int value){
        if(tl==tr){
            t[v]=value;
        }
        else {
            int tm=(tl+tr)/2;
            if(index<=tm){
                update(v*2,tl,tm,index,value);
            }
            else {
                update(v*2+1,tm+1,tr,index,value);
            }
            t[v]=(t[v*2]^t[v*2+1]);
        }
    }
};
segtree seg[2];
/*
int brute(int l,int r){
    int ans=0;
            for(int i=l;i<=r;i++){
                for(int j=i;j<=r;j++){
                    ans^=seg.query(1,1,n,i,j);
                }
            }
            return ans;
}
*/
int solve(int l,int r,int o){
    if((r-l+1)%2==0)return 0;
    if(l==r)return a[l];
    return seg[o].query(1,1,n,l,r);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        if(i%2==0)A[i]=a[i];
    }
    seg[0].build(1,1,n);
    for(int i=1;i<=n;i++){
        if(i%2==0)A[i]=0;
        else A[i]=a[i];
    }
    seg[1].build(1,1,n);
    while(q--){
        int o;
        cin>>o;
        if(o==1){
            int i,x;
            cin>>i>>x;
            seg[i%2].update(1,1,n,i,x);
        }
        else {
            int l,r;
            cin>>l>>r;
            cout<<solve(l,r,l%2);
            cout<<"\n";
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 17688 KB Output is correct
2 Correct 107 ms 15944 KB Output is correct
3 Correct 108 ms 15980 KB Output is correct
4 Correct 94 ms 16132 KB Output is correct
5 Correct 91 ms 15940 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 124 ms 17688 KB Output is correct
16 Correct 107 ms 15944 KB Output is correct
17 Correct 108 ms 15980 KB Output is correct
18 Correct 94 ms 16132 KB Output is correct
19 Correct 91 ms 15940 KB Output is correct
20 Correct 103 ms 15344 KB Output is correct
21 Incorrect 108 ms 15352 KB Output isn't correct
22 Halted 0 ms 0 KB -