oj.uz

Submission #890397

# Submission time Handle Problem Language Result Execution time Memory
890397 2023-12-21T05:59:38 Z rahidilbayramli XORanges (eJOI19_xoranges) C++17
100 / 100
 93 ms 17492 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define pb push_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll sz = 2e5+5;
ll v[sz], a[sz], b[sz], segtree1[4*sz], segtree2[4*sz];
void build1(ll v, ll l, ll r)
{
    if(l == r)
        segtree1[v] = a[l];
    else
    {
        ll mid = (l + r) / 2;
        build1(2*v, l, mid);
        build1(2*v+1, mid+1, r);
        segtree1[v] = (segtree1[2*v] ^ segtree1[2*v+1]);
    }
}
void build2(ll v, ll l, ll r)
{
    if(l == r)
        segtree2[v] = b[l];
    else
    {
        ll mid = (l + r) / 2;
        build2(2*v, l, mid);
        build2(2*v+1, mid+1, r);
        segtree2[v] = (segtree2[2*v] ^ segtree2[2*v+1]);
    }
}
void update1(ll v, ll l, ll r, ll pos, ll val)
{
    if(l == r)
        segtree1[v] = val;
    else
    {
        ll mid = (l + r) / 2;
        if(pos <= mid)
            update1(2*v, l, mid, pos, val);
        else
            update1(2*v+1, mid+1, r, pos, val);
        segtree1[v] = (segtree1[2*v] ^ segtree1[2*v+1]);
    }
}
void update2(ll v, ll l, ll r, ll pos, ll val)
{
    if(l == r)
        segtree2[v] = val;
    else
    {
        ll mid = (l + r) / 2;
        if(pos <= mid)
            update2(2*v, l, mid, pos, val);
        else
            update2(2*v+1, mid+1, r, pos, val);
        segtree2[v] = (segtree2[2*v] ^ segtree2[2*v+1]);
    }
}
ll findans1(ll v, ll l, ll r, ll tl, ll tr)
{
    if(tl > tr)
        return 0;
    else    if(l == tl && r == tr)
        return segtree1[v];
    else
    {
        ll mid = (l + r) / 2;
        ll lans, rans;
        lans = findans1(2*v, l, mid, tl, min(mid, tr));
        rans = findans1(2*v+1, mid+1, r, max(mid+1, tl), tr);
        return (lans^rans);
    }
}
ll findans2(ll v, ll l, ll r, ll tl, ll tr)
{
    if(tl > tr)
        return 0;
    else    if(l == tl && r == tr)
        return segtree2[v];
    else
    {
        ll mid = (l + r) / 2;
        ll lans, rans;
        lans = findans2(2*v, l, mid, tl, min(mid, tr));
        rans = findans2(2*v+1, mid+1, r, max(mid+1, tl), tr);
        return (lans^rans);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests = 1;
    //cin >> tests;
    while(tests--)
    {
        ll n, q, i, j, n1 = 0, n2 = 0;
        cin >> n >> q;
        for(i = 1; i <= n; i++)
            cin >> v[i];
        for(i = 1; i <= n; i++)
        {
            if(i % 2){
                a[(i+1)/2] = v[i];
                n1++;
            }
            else{
                b[i/2] = v[i];
                n2++;
            }
        }
        build1(1, 1, n1);
        build2(1, 1, n2);
        while(q--)
        {
            ll type;
            cin >> type;
            if(type == 1)
            {
                ll pos, val;
                cin >> pos >> val;
                if(pos % 2)
                    update1(1, 1, n1, (pos+1)/2, val);
                else
                    update2(1, 1, n2, pos/2, val);
            }
            else
            {
                ll l, r;
                cin >> l >> r;
                if((r - l + 1) % 2 == 0)
                    cout << "0\n";
                else{
                    if(l % 2)
                    {
                        l = (l + 1) / 2;
                        r = (r + 1) / 2;
                        cout << findans1(1, 1, n1, l, r) << "\n";
                    }
                    else
                    {
                        l /= 2;
                        r /= 2;
                        cout << findans2(1, 1, n2, l, r) << "\n";
                    }
                }
            }
        }
    }
}

Compilation message

xoranges.cpp: In function 'int main()':
xoranges.cpp:110:21: warning: unused variable 'j' [-Wunused-variable]
  110 |         ll n, q, i, j, n1 = 0, n2 = 0;
      |                     ^

Subtask #1
12.0 / 12.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 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 6744 KB Output is correct
2 Correct 1 ms 6616 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 6488 KB Output is correct

Subtask #3
25.0 / 25.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 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6744 KB Output is correct
7 Correct 1 ms 6616 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 3 ms 6748 KB Output is correct
14 Correct 3 ms 6748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 17352 KB Output is correct
2 Correct 91 ms 17488 KB Output is correct
3 Correct 93 ms 17480 KB Output is correct
4 Correct 83 ms 17028 KB Output is correct
5 Correct 83 ms 16996 KB Output is correct

Subtask #5
25.0 / 25.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 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6744 KB Output is correct
7 Correct 1 ms 6616 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 3 ms 6748 KB Output is correct
14 Correct 3 ms 6748 KB Output is correct
15 Correct 91 ms 17352 KB Output is correct
16 Correct 91 ms 17488 KB Output is correct
17 Correct 93 ms 17480 KB Output is correct
18 Correct 83 ms 17028 KB Output is correct
19 Correct 83 ms 16996 KB Output is correct
20 Correct 86 ms 17072 KB Output is correct
21 Correct 90 ms 17492 KB Output is correct
22 Correct 86 ms 17144 KB Output is correct
23 Correct 83 ms 17020 KB Output is correct
24 Correct 87 ms 17028 KB Output is correct