oj.uz

Submission #999760

# Submission time Handle Problem Language Result Execution time Memory
999760 2024-06-16T06:27:28 Z ayankarimova XORanges (eJOI19_xoranges) C++14
100 / 100
 91 ms 18972 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll sz=2e5+5;
ll s1[sz*4], s2[sz*4], a[sz], b[sz];
void build1(ll l, ll r, ll in)
{
    if(l==r){
        s1[in]=a[l];
        return;
    }
    ll mid=(l+r)/2;
    build1(l, mid, in*2);
    build1(mid+1, r, in*2+1);
    s1[in]=(s1[in*2]^s1[in*2+1]);
}
void build2(ll l, ll r, ll in)
{
    if(l==r){
        s2[in]=b[l];
        return;
    }
    ll mid=(l+r)/2;
    build2(l, mid, in*2);
    build2(mid+1, r, in*2+1);
    s2[in]=(s2[in*2]^s2[in*2+1]);
}
void update1(ll l, ll r, ll in, ll ind, ll val)
{
    if(ind<l || ind>r) return;
    if(l==r){
        s1[in]=val;
        return;
    }
    ll mid=(l+r)/2;
    update1(l, mid, in*2, ind, val);
    update1(mid+1, r, in*2+1, ind, val);
    s1[in]=(s1[in*2]^s1[in*2+1]);
}
void update2(ll l, ll r, ll in, ll ind, ll val)
{
    if(ind<l || ind>r) return;
    if(l==r){
        s2[in]=val;
        return;
    }
    ll mid=(l+r)/2;
    update2(l, mid, in*2, ind, val);
    update2(mid+1, r, in*2+1, ind, val);
    s2[in]=(s2[in*2]^s2[in*2+1]);
}
ll ans1(ll l, ll r, ll in, ll ql, ll qr)
{
    if(ql>r || qr<l) return 0;
    if(ql<=l && r<=qr){
        return s1[in];
    }
    ll mid=(l+r)/2;
    return (ans1(l, mid, in*2, ql, qr)^ans1(mid+1, r, in*2+1, ql, qr));
}
ll ans2(ll l, ll r, ll in, ll ql, ll qr)
{
    if(ql>r || qr<l) return 0;
    if(ql<=l && r<=qr){
        return s2[in];
    }
    ll mid=(l+r)/2;
    return (ans2(l, mid, in*2, ql, qr)^ans2(mid+1, r, in*2+1, ql, qr));
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n, q;
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        if(i%2){
            cin>>a[i];
        }
        else{
            cin>>b[i];
        }
    }
    build1(1, n, 1);
    build2(1, n, 1);
    while(q--){
        ll t, l, r;
        cin>>t>>l>>r;
        if(t==1){
            if(l%2){
                update1(1, n, 1, l, r);
            }
            else{
                update2(1, n, 1, l, r);
            }
        }
        else{
            if((l-r+1)%2==0){
                cout<<0<<endl;
            }
            else{
                if(l%2){
                    cout<<ans1(1, n, 1, l, r)<<endl;
                }
                else{
                    cout<<ans2(1, n, 1, l, r)<<endl;
                }
            }
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6612 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 3 ms 6744 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 18972 KB Output is correct
2 Correct 88 ms 18784 KB Output is correct
3 Correct 84 ms 18772 KB Output is correct
4 Correct 81 ms 18768 KB Output is correct
5 Correct 81 ms 18920 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6612 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 3 ms 6744 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 82 ms 18972 KB Output is correct
16 Correct 88 ms 18784 KB Output is correct
17 Correct 84 ms 18772 KB Output is correct
18 Correct 81 ms 18768 KB Output is correct
19 Correct 81 ms 18920 KB Output is correct
20 Correct 89 ms 18508 KB Output is correct
21 Correct 86 ms 18512 KB Output is correct
22 Correct 91 ms 18516 KB Output is correct
23 Correct 88 ms 18824 KB Output is correct
24 Correct 79 ms 18940 KB Output is correct