oj.uz

Submission #284054

# Submission time Handle Problem Language Result Execution time Memory
284054 2020-08-26T15:25:07 Z Patrusheva_Anna XORanges (eJOI19_xoranges) C++14
100 / 100
 157 ms 9276 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")

#define ll long long
#define pb push_back
#define F first
#define S second
#define ull unsigned long long
#define pii pair < int, int >
#define ld long double


using namespace std;
using namespace __gnu_pbds;

mt19937 gen(time(0));
template <typename T>
using ordered_set=tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 100000 * 5;
int ta[N];
int tb[N];

void change_a(int v, int tl, int tr, int in ,int val)
{
    if (tl >= in && tr<= in)
    {
        ta[v] = val;
        return;
    }

    if (tl > in || tr < in) return;
    int mid = (tl + tr) / 2;

    change_a(v * 2, tl, mid, in , val);
    change_a(v * 2 + 1, mid + 1, tr, in , val);

    ta[v] = ta[v * 2] ^ ta[v * 2 + 1];
    return;
}

void change_b(int v, int tl, int tr, int in ,int val)
{
    if (tl >= in && tr<= in)
    {
        tb[v] = val;
        return;
    }

    if (tl > in || tr < in) return;
    int mid = (tl + tr) / 2;

    change_b(v * 2, tl, mid, in , val);
    change_b(v * 2 + 1, mid + 1, tr, in , val);

    tb[v] = tb[v * 2] ^ tb[v * 2 + 1];
    return;
}

int F_a(int v, int tl, int tr, int l, int r)
{
    if (tl >= l && tr <= r)
    {
        return ta[v];
    }
    if (tl > r || tr < l) return 0;
    int mid = (tl + tr) / 2;

    return F_a(v * 2, tl, mid, l, r) ^ F_a(v * 2 + 1, mid + 1, tr, l, r);

}

int F_b(int v, int tl, int tr, int l, int r)
{
    if (tl >= l && tr <= r)
    {
        return tb[v];
    }
    if (tl > r || tr < l) return 0;
    int mid = (tl + tr) / 2;

    return F_b(v * 2, tl, mid, l, r) ^ F_b(v * 2 + 1, mid + 1, tr, l, r);

}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#else

#endif


    int n;
    cin >> n;
    int q;
    cin >> q;

    vector < int > a, b;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (i % 2 == 0) a.pb(x);
        else b.pb(x);
    }


    int ka = 1;
    while (ka < (int)a.size()) ka *= 2;

    int kb = 1;
    while (kb < (int)b.size()) kb *= 2;

    for (int i = ka; i < ka + (int)a.size(); i++)
        ta[i] = a[i - ka];

    for (int i = ka - 1; i >= 1; i--)
        ta[i] = ta[i * 2] ^ ta[i * 2 + 1];



    for (int i = kb; i < kb + (int)b.size(); i++)
        tb[i] = b[i - kb];

    for (int i = kb - 1; i >= 1; i--)
        tb[i] = tb[i * 2] ^ tb[i * 2 + 1];


    while (q--)
    {
        int z;
        cin >> z;
        if (z == 1)
        {
            int in, val;
            cin >> in >> val;
            if (in % 2 == 1)
            {
                change_a(1, 1, ka, in / 2 + 1, val);
            }
            else
                change_b(1, 1, kb, in / 2, val);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            if ((r - l + 1) % 2 == 0) cout << 0 << "\n";
            else
            {
                int kol = r - l + 1;
                kol = kol % 2 + kol / 2;
                if (l % 2 == 1)
                    cout << F_a(1, 1, ka, 1 + l / 2, l / 2 + kol) << "\n";
                else
                    cout << F_b(1, 1, kb, l / 2, l / 2 + kol - 1) << "\n";

//                cout << l % 2 + l / 2 << ' ' << kol + l / 2  - (1 - l % 2)<< "\n";
            }
        }
    }




    return 0;

}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 416 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 3 ms 640 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 4404 KB Output is correct
2 Correct 149 ms 9276 KB Output is correct
3 Correct 145 ms 9196 KB Output is correct
4 Correct 130 ms 8936 KB Output is correct
5 Correct 130 ms 8936 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 416 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Correct 143 ms 4404 KB Output is correct
16 Correct 149 ms 9276 KB Output is correct
17 Correct 145 ms 9196 KB Output is correct
18 Correct 130 ms 8936 KB Output is correct
19 Correct 130 ms 8936 KB Output is correct
20 Correct 152 ms 9052 KB Output is correct
21 Correct 151 ms 8940 KB Output is correct
22 Correct 157 ms 8940 KB Output is correct
23 Correct 135 ms 8848 KB Output is correct
24 Correct 135 ms 8936 KB Output is correct