oj.uz

Submission #658721

# Submission time Handle Problem Language Result Execution time Memory
658721 2022-11-14T14:04:55 Z Banan XORanges (eJOI19_xoranges) C++17
100 / 100
 146 ms 16072 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int long long
#define double long double
#define endl '\n'
#define sz(a) (int)a.size()
#define pb push_back
#define fs first
#define sc second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
int const INF = LONG_LONG_MAX;

int n, q, a[200005], ev[800040], od[800040];

void build(int v, int l, int r, int* tree,int parity)
{
    if(l==r)
    {
        if((l&1)==parity){tree[v]=a[l];}else{tree[v]=0;}
    }
    else
    {
        int mid=(l+r)/2;
        build(2*v, l, mid, tree, parity);
        build(2*v+1, mid+1, r, tree, parity);
        tree[v]=(tree[2*v]^tree[2*v+1]);
    }
}

void update(int v, int l, int r, int* tree, int pos)
{
    if(l==r)
    {
        tree[v]=a[l];
    }
    else
    {
        int mid=(l+r)/2;
        if(mid>=pos)
        {
            update(2*v, l, mid, tree, pos);
        }
        else
        {
            update(2*v+1, mid+1, r, tree, pos);
        }
        tree[v]=(tree[2*v]^tree[2*v+1]);
    }
}

int ask(int v, int l, int r, int* tree, int sl, int sr)
{
    if(r<sl || l>sr){return 0;}
    if(l==sl && r==sr)
    {
        return tree[v];
    }
    else
    {
        int mid=(l+r)/2;
        int v1=ask(2*v, l, mid, tree, sl, min(mid, sr));
        int v2=ask(2*v+1, mid+1, r, tree, max(mid+1, sl), sr);
        return v1^v2;
    }
}


void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    build(1, 1, n, ev, 0);
    build(1, 1, n, od, 1);

    while(q--)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int pos, val;
            cin>>pos>>val;
            a[pos]=val;
            if(pos&1)
            {
                update(1, 1, n, od, pos);
            }
            else
            {
                update(1, 1, n, ev, pos);
            }
        }
        if(t==2)
        {
            int l, r;
            cin>>l>>r;
            if((r-l+1)&1)
            {
                if(l&1)
                {
                    cout<<ask(1, 1, n, od, l, r)<<endl;
                }
                else
                {
                    cout<<ask(1, 1, n, ev, l, r)<<endl;
                }
            }
            else
            {
                cout<<0<<endl;
            }
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int tc=1;
    //cin>>tc;
    while(tc--)
    {
        solve();
    }
    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 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 728 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 3 ms 724 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 16072 KB Output is correct
2 Correct 134 ms 16040 KB Output is correct
3 Correct 134 ms 16072 KB Output is correct
4 Correct 112 ms 15724 KB Output is correct
5 Correct 116 ms 15792 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 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 728 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 3 ms 724 KB Output is correct
15 Correct 125 ms 16072 KB Output is correct
16 Correct 134 ms 16040 KB Output is correct
17 Correct 134 ms 16072 KB Output is correct
18 Correct 112 ms 15724 KB Output is correct
19 Correct 116 ms 15792 KB Output is correct
20 Correct 132 ms 15820 KB Output is correct
21 Correct 146 ms 15768 KB Output is correct
22 Correct 131 ms 15960 KB Output is correct
23 Correct 114 ms 15776 KB Output is correct
24 Correct 111 ms 15708 KB Output is correct