oj.uz

Submission #455330

# Submission time Handle Problem Language Result Execution time Memory
455330 2021-08-05T21:32:56 Z kkk XORanges (eJOI19_xoranges) C++14
100 / 100
 183 ms 20232 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long a[1000003],tree[4000000][3];
void build_tree(long long l,long long r,long long ind)
{
    if(l==r)
    {
        if(l%2==0)tree[ind][0]=a[l];
        else tree[ind][1]=a[l];
        return;
    }
    long long mid=(l+r)/2;

    build_tree(l,mid,2*ind);
    build_tree(mid+1,r,2*ind+1);

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

    if(l==r)
    {
        if(l%2==0)tree[ind][0]=val;
        else tree[ind][1]=val;
        return;
    }
    long long mid=(l+r)/2;

    update(l,mid,pos,val,2*ind);
    update(mid+1,r,pos,val,2*ind+1);

    tree[ind][0]=(tree[2*ind][0]^tree[2*ind+1][0]);
    tree[ind][1]=(tree[2*ind][1]^tree[2*ind+1][1]);

}
long long query(long long le,long long ri,long long l,long long r,long long ind,int t)
{
    if(le>r || ri<l)return 0;

    if(l<=le && ri<=r)
    {
        if(t==0)return tree[ind][0];
        else return tree[ind][1];
    }
    long long mid=(le+ri)/2, t2;

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

    long long n,m,q,j,i,b,ans=0,t,l,r;


    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build_tree(1,n,1);
    for(i=0;i<q;i++)
    {
        cin>>t;
        if(t==1)
        {
            cin>>l>>r;
            update(1,n,l,r,1);
        }
        else
        {
            cin>>l>>r;
            if((r-l+1)%2==0)
            {
                cout<<0<<endl;
                continue;
            }

            cout<<query(1,n,l,r,1,l%2)<<endl;
        }

    }


}

Compilation message

xoranges.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int, int)':
xoranges.cpp:49:30: warning: unused variable 't2' [-Wunused-variable]
   49 |     long long mid=(le+ri)/2, t2;
      |                              ^~
xoranges.cpp: In function 'int main()':
xoranges.cpp:59:17: warning: unused variable 'm' [-Wunused-variable]
   59 |     long long n,m,q,j,i,b,ans=0,t,l,r;
      |                 ^
xoranges.cpp:59:21: warning: unused variable 'j' [-Wunused-variable]
   59 |     long long n,m,q,j,i,b,ans=0,t,l,r;
      |                     ^
xoranges.cpp:59:25: warning: unused variable 'b' [-Wunused-variable]
   59 |     long long n,m,q,j,i,b,ans=0,t,l,r;
      |                         ^
xoranges.cpp:59:27: warning: unused variable 'ans' [-Wunused-variable]
   59 |     long long n,m,q,j,i,b,ans=0,t,l,r;
      |                           ^~~

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 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 332 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 384 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 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 384 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 844 KB Output is correct
12 Correct 4 ms 844 KB Output is correct
13 Correct 4 ms 844 KB Output is correct
14 Correct 5 ms 848 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 15336 KB Output is correct
2 Correct 171 ms 20232 KB Output is correct
3 Correct 175 ms 20172 KB Output is correct
4 Correct 145 ms 19876 KB Output is correct
5 Correct 144 ms 19780 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 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 384 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 844 KB Output is correct
12 Correct 4 ms 844 KB Output is correct
13 Correct 4 ms 844 KB Output is correct
14 Correct 5 ms 848 KB Output is correct
15 Correct 178 ms 15336 KB Output is correct
16 Correct 171 ms 20232 KB Output is correct
17 Correct 175 ms 20172 KB Output is correct
18 Correct 145 ms 19876 KB Output is correct
19 Correct 144 ms 19780 KB Output is correct
20 Correct 183 ms 19980 KB Output is correct
21 Correct 178 ms 19908 KB Output is correct
22 Correct 179 ms 19920 KB Output is correct
23 Correct 148 ms 19776 KB Output is correct
24 Correct 147 ms 19876 KB Output is correct