oj.uz

Submission #448536

# Submission time Handle Problem Language Result Execution time Memory
448536 2021-07-30T13:05:21 Z Tenis0206 XORanges (eJOI19_xoranges) C++11
100 / 100
 208 ms 10380 KB 
#include <bits/stdc++.h>

using namespace std;
struct arbore_de_intervale
{
    int par,imp;
};
arbore_de_intervale ai[1000005];
int n,q,v[200005];
void update(int poz, int val, int nod, int a, int b)
{
    if(a==b)
    {
        if(a%2==1)
        {
            ai[nod].imp = val;
            ai[nod].par = 0;
        }
        else
        {
            ai[nod].par = val;
            ai[nod].imp = 0;
        }
        return;
    }
    int mij = (a+b)>>1;
    if(poz<=mij)
    {
        update(poz,val,nod*2,a,mij);
    }
    else
    {
        update(poz,val,nod*2+1,mij+1,b);
    }
    ai[nod].par = (ai[nod*2].par ^ ai[nod*2+1].par);
    ai[nod].imp = (ai[nod*2].imp ^ ai[nod*2+1].imp);
}
int query(int qa, int qb, int paritate, int nod, int a, int b)
{
    if(qa<=a && qb>=b)
    {
        if(paritate%2==0)
        {
            return ai[nod].par;
        }
        return ai[nod].imp;
    }
    int mij = (a+b)>>1;
    int rez1 = 0, rez2 = 0;
    if(qa<=mij)
    {
        rez1 = query(qa,qb,paritate,nod*2,a,mij);
    }
    if(qb>mij)
    {
        rez2 = query(qa,qb,paritate,nod*2+1,mij+1,b);
    }
    return (rez1 ^ rez2);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
        update(i,v[i],1,1,n);
    }
    for(int i=1; i<=q; i++)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int poz,val;
            cin>>poz>>val;
            update(poz,val,1,1,n);
        }
        else
        {
            int x,y;
            cin>>x>>y;
            if((y-x+1)%2==0)
            {
                cout<<0<<'\n';
                continue;
            }
            if(x%2==1)
            {
                cout<<query(x,y,1,1,1,n)<<'\n';
            }
            else
            {
                cout<<query(x,y,0,1,1,n)<<'\n';
            }
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

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
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 10380 KB Output is correct
2 Correct 190 ms 9596 KB Output is correct
3 Correct 187 ms 9480 KB Output is correct
4 Correct 170 ms 9440 KB Output is correct
5 Correct 170 ms 9456 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 4 ms 460 KB Output is correct
14 Correct 4 ms 460 KB Output is correct
15 Correct 208 ms 10380 KB Output is correct
16 Correct 190 ms 9596 KB Output is correct
17 Correct 187 ms 9480 KB Output is correct
18 Correct 170 ms 9440 KB Output is correct
19 Correct 170 ms 9456 KB Output is correct
20 Correct 186 ms 8888 KB Output is correct
21 Correct 185 ms 8948 KB Output is correct
22 Correct 187 ms 8924 KB Output is correct
23 Correct 173 ms 9492 KB Output is correct
24 Correct 171 ms 9600 KB Output is correct