oj.uz

Submission #753090

# Submission time Handle Problem Language Result Execution time Memory
753090 2023-06-04T14:40:10 Z MateiKing80 XORanges (eJOI19_xoranges) C++14
100 / 100
 532 ms 4400 KB 
#include <iostream>

using namespace std;

int v[200005];
int aint1[1<<19];
int aint2[1<<19];


void build1(int poz, int st, int dr)
{
    if(st==dr)
    {
        aint1[poz]=v[2*st-1];
        return;
    }
    int mid=(st+dr)/2;
    build1(2*poz,st,mid);
    build1(2*poz+1,mid+1,dr);
    aint1[poz]=(aint1[2*poz]^aint1[2*poz+1]);
}

void build2(int poz, int st, int dr)
{
    if(st==dr)
    {
        aint2[poz]=v[2*st];
        return;
    }
    int mid=(st+dr)/2;
    build2(2*poz,st,mid);
    build2(2*poz+1,mid+1,dr);
    aint2[poz]=(aint2[2*poz]^aint2[2*poz+1]);
}


void update1(int poz, int st, int dr, int a, int b)
{
    if(st==dr)
    {
        aint1[poz]=b;
        return;
    }
    int mid=(st+dr)/2;
    if(a<=mid)
        update1(2*poz,st,mid,a,b);
    else
        update1(2*poz+1,mid+1,dr,a,b);
    aint1[poz]=(aint1[2*poz]^aint1[2*poz+1]);
}

void update2(int poz, int st, int dr, int a, int b)
{
    if(st==dr)
    {
        aint2[poz]=b;
        return;
    }
    int mid=(st+dr)/2;
    if(a<=mid)
        update2(2*poz,st,mid,a,b);
    else
        update2(2*poz+1,mid+1,dr,a,b);
    aint2[poz]=(aint2[2*poz]^aint2[2*poz+1]);
}


int query1(int poz, int st, int dr, int a, int b)
{
    if(a<=st && dr<=b)
        return aint1[poz];
    int mid=(st+dr)/2;
    if(b<=mid)
        return query1(2*poz,st,mid,a,b);
    if(mid<a)
        return query1(2*poz+1,mid+1,dr,a,b);
    return (query1(2*poz,st,mid,a,b)^query1(2*poz+1,mid+1,dr,a,b));
}

int query2(int poz, int st, int dr, int a, int b)
{
    if(a<=st && dr<=b)
        return aint2[poz];
    int mid=(st+dr)/2;
    if(b<=mid)
        return query2(2*poz,st,mid,a,b);
    if(mid<a)
        return query2(2*poz+1,mid+1,dr,a,b);
    return (query2(2*poz,st,mid,a,b)^query2(2*poz+1,mid+1,dr,a,b));
}




int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    build1(1,1,(n+1)/2);
    build2(1,1,n/2);
    for(int i=0;i<q;i++)
    {
        int cer,a,b;
        cin>>cer>>a>>b;
        if(cer==1)
        {
            if( (a%2) == 1)
                update1(1,1,(n+1)/2,a/2+1,b);
            else
                update2(1,1,n/2,a/2,b);
        }
        else
        {
            if((b-a)%2==1)
                cout<<0<<'\n';
            else if((a%2)==1)
                cout<<query1(1,1,(n+1)/2,a/2+1,b/2+1)<<'\n';
            else
                cout<<query2(1,1,n/2,a/2,b/2)<<'\n';
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 9 ms 424 KB Output is correct
12 Correct 9 ms 416 KB Output is correct
13 Correct 13 ms 440 KB Output is correct
14 Correct 16 ms 340 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 4244 KB Output is correct
2 Correct 502 ms 4256 KB Output is correct
3 Correct 532 ms 4324 KB Output is correct
4 Correct 468 ms 4400 KB Output is correct
5 Correct 487 ms 4340 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 9 ms 424 KB Output is correct
12 Correct 9 ms 416 KB Output is correct
13 Correct 13 ms 440 KB Output is correct
14 Correct 16 ms 340 KB Output is correct
15 Correct 501 ms 4244 KB Output is correct
16 Correct 502 ms 4256 KB Output is correct
17 Correct 532 ms 4324 KB Output is correct
18 Correct 468 ms 4400 KB Output is correct
19 Correct 487 ms 4340 KB Output is correct
20 Correct 390 ms 3640 KB Output is correct
21 Correct 396 ms 3776 KB Output is correct
22 Correct 377 ms 3724 KB Output is correct
23 Correct 491 ms 4208 KB Output is correct
24 Correct 526 ms 4176 KB Output is correct