oj.uz

Submission #455332

# Submission time Handle Problem Language Result Execution time Memory
455332 2021-08-05T21:35:14 Z daisy XORanges (eJOI19_xoranges) C++17
100 / 100
 176 ms 6516 KB 
#include<iostream>
#define endl '\n'
using namespace std;
int tree[800005][2],m[2000005];
void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node][l%2]=m[l];
        return;
    }
    int mid=(l+r)/2;

    build(2*node,l,mid);
    build(2*node+1,mid+1,r);

    tree[node][0]=(tree[2*node][0]^tree[2*node+1][0]);
    tree[node][1]=(tree[2*node][1]^tree[2*node+1][1]);
}
void update(int node,int l,int r,int val,int p)
{
    if(r<p || l>p) return;

    if(l==r)
    {
        tree[node][l%2]=val;
        return;
    }
     int mid=(l+r)/2;

    update(2*node,l,mid,val,p);
    update(2*node+1,mid+1,r,val,p);

    tree[node][0]=tree[2*node][0]^tree[2*node+1][0];
    tree[node][1]=tree[2*node][1]^tree[2*node+1][1];
}
int query(int node,int l,int r,int le, int ri, int t)
{
    if(l>ri || r<le) return 0;
    if(l>=le && r<=ri) return tree[node][t%2];

     int mid=(l+r)/2;

    return (query(2*node,l,mid,le,ri,t)^query(2*node+1,mid+1,r,le,ri,t));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,q,x,y,c;
    cin>>n>>q;

    for(int i=1;i<=n;i++)
        cin>>m[i];

    build(1,1,n);

    for(int i=0;i<q;i++)
    {
        cin>>c>>x>>y;
        if(c==1)
        {
            update(1,1,n,y,x);
        }
        if(c==2)
        {
            if((x-y+1)%2==0) cout<<0<<endl;
            else
            cout<<query(1,1,n,x,y,x%2)<<endl;
        }
    }

}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 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 484 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 6516 KB Output is correct
2 Correct 168 ms 6388 KB Output is correct
3 Correct 172 ms 6352 KB Output is correct
4 Correct 150 ms 6292 KB Output is correct
5 Correct 144 ms 6404 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 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 484 KB Output is correct
15 Correct 176 ms 6516 KB Output is correct
16 Correct 168 ms 6388 KB Output is correct
17 Correct 172 ms 6352 KB Output is correct
18 Correct 150 ms 6292 KB Output is correct
19 Correct 144 ms 6404 KB Output is correct
20 Correct 164 ms 5740 KB Output is correct
21 Correct 161 ms 5776 KB Output is correct
22 Correct 173 ms 5792 KB Output is correct
23 Correct 149 ms 6212 KB Output is correct
24 Correct 148 ms 6276 KB Output is correct