oj.uz

Submission #810981

# Submission time Handle Problem Language Result Execution time Memory
810981 2023-08-06T18:52:58 Z andrewp XORanges (eJOI19_xoranges) C++17
100 / 100
 295 ms 11212 KB 
//Dedicated to my love, ivaziva
#include <bits/stdc++.h>

using namespace std;
int n,q;
const int ivamanjeod3=200007;
int iva[ivamanjeod3],ivapavODD[ivamanjeod3*4],ivapavEVEN[ivamanjeod3*4];
void IVAIVA(int v,int tl,int tr,int i,int x)
{
    if(tl==tr)
    {
        if(tl%2==1)
        {
            ivapavODD[v]=x;
            ivapavEVEN[v]=0;
        }
        else
        {
            ivapavEVEN[v]=x;
            ivapavODD[v]=0;
        }
        return;
    }
    int mid=(tl+tr)/2;
    if(i<=mid) IVAIVA(2*v,tl,mid,i,x);
    else IVAIVA(2*v+1,mid+1,tr,i,x);
    ivapavODD[v]=(ivapavODD[2*v]^ivapavODD[2*v+1]);
    ivapavEVEN[v]=(ivapavEVEN[2*v]^ivapavEVEN[2*v+1]);
}
int IVAIVAIVA1(int v,int tl,int tr,int l,int r)
{
    if(l>r) return 0;
    if(tl==l&&tr==r) return ivapavODD[v];
    int mid=(tl+tr)/2;
    return (IVAIVAIVA1(2*v,tl,mid,l,min(mid,r))^IVAIVAIVA1(2*v+1,mid+1,tr,max(mid+1,l),r));
}
int IVAIVAIVA2(int v,int tl,int tr,int l,int r)
{
    if(l>r) return 0;
    if(tl==l&&tr==r) return ivapavEVEN[v];
    int mid=(tl+tr)/2;
    return (IVAIVAIVA2(2*v,tl,mid,l,min(mid,r))^IVAIVAIVA2(2*v+1,mid+1,tr,max(mid+1,l),r));
}
void IVA(int v,int tl,int tr)
{
    if(tl==tr){
        if(tl%2==1)
        {
            ivapavODD[v]=iva[tl];
            ivapavEVEN[v]=0;
        }
        else
        {
            ivapavODD[v]=0;
            ivapavEVEN[v]=iva[tl];
        }
        return;
    }
    int mid=(tl+tr)/2;
    IVA(2*v,tl,mid);
    IVA(2*v+1,mid+1,tr);
    ivapavODD[v]=ivapavODD[2*v]^ivapavODD[2*v+1];
    ivapavEVEN[v]=ivapavEVEN[2*v]^ivapavEVEN[2*v+1];
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>iva[i];
    }
    IVA(1,1,n);
    while(q--)
    {
        int tp,l,r;
        cin>>tp>>l>>r;
        if(tp==1)
        {
            int i=l,x=r;
            IVAIVA(1,1,n,i,x);
        }
        else
        {
            int sz=r-l+1;
            if(sz%2==0)
            {
                cout<<0<<endl;
            }
            else
            {
                if(l%2==1)
                {
                    cout<<IVAIVAIVA1(1,1,n,l,r)<<endl;
                }
                else
                {
                    cout<<IVAIVAIVA2(1,1,n,l,r)<<endl;
                }
            }
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.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 #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 332 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 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
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 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 6 ms 624 KB Output is correct
13 Correct 7 ms 600 KB Output is correct
14 Correct 7 ms 512 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 11212 KB Output is correct
2 Correct 293 ms 10556 KB Output is correct
3 Correct 288 ms 10564 KB Output is correct
4 Correct 278 ms 10556 KB Output is correct
5 Correct 281 ms 10560 KB Output is correct

Subtask #5
25.0 / 25.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
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 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 6 ms 624 KB Output is correct
13 Correct 7 ms 600 KB Output is correct
14 Correct 7 ms 512 KB Output is correct
15 Correct 295 ms 11212 KB Output is correct
16 Correct 293 ms 10556 KB Output is correct
17 Correct 288 ms 10564 KB Output is correct
18 Correct 278 ms 10556 KB Output is correct
19 Correct 281 ms 10560 KB Output is correct
20 Correct 189 ms 9996 KB Output is correct
21 Correct 195 ms 9928 KB Output is correct
22 Correct 194 ms 9972 KB Output is correct
23 Correct 289 ms 10564 KB Output is correct
24 Correct 284 ms 10680 KB Output is correct