oj.uz

Submission #819812

# Submission time Handle Problem Language Result Execution time Memory
819812 2023-08-10T13:50:27 Z Andrijanikolic73 XORanges (eJOI19_xoranges) C++17
75 / 100
 307 ms 17628 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<<endl;
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 340 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 0 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 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 5 ms 596 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Correct 7 ms 728 KB Output is correct
14 Correct 9 ms 728 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 12836 KB Output is correct
2 Correct 307 ms 17628 KB Output is correct
3 Correct 299 ms 17624 KB Output is correct
4 Correct 295 ms 17320 KB Output is correct
5 Correct 301 ms 17276 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 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 5 ms 596 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Correct 7 ms 728 KB Output is correct
14 Correct 9 ms 728 KB Output is correct
15 Correct 304 ms 12836 KB Output is correct
16 Correct 307 ms 17628 KB Output is correct
17 Correct 299 ms 17624 KB Output is correct
18 Correct 295 ms 17320 KB Output is correct
19 Correct 301 ms 17276 KB Output is correct
20 Correct 208 ms 17324 KB Output is correct
21 Incorrect 201 ms 17304 KB Output isn't correct
22 Halted 0 ms 0 KB -