oj.uz

Submission #469360

# Submission time Handle Problem Language Result Execution time Memory
469360 2021-08-31T15:32:20 Z myvaluska XORanges (eJOI19_xoranges) C++14
55 / 100
 211 ms 6268 KB 
// najsprostejsiasarica.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
// ejoiden2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
// trenujflashinka.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
// ejoiden2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int maxn = 1 << 17;
vector<int>l(maxn * 2);
vector<int>r(maxn * 2);
vector<int> xor1 (maxn * 2);
vector<int>xor2(maxn * 2);
void update(int i, int vr, int hod)
{
    if (i<l[vr] || i>r[vr])
    {
        return;
    }
    if (i == l[vr] && i == r[vr])
    {
        if (i % 2 == 0)
        {
            xor1[vr] = hod;
            return;
        }
        else
        {
            xor2[vr] = hod;
            return;
        }
    }
    update(i, vr * 2 + 1, hod);
    update(i, vr * 2 + 2, hod);
    xor1[vr] = xor1[vr * 2 + 1] ^ xor1[vr * 2 + 2];
    xor2[vr] = xor2[vr * 2 + 1] ^ xor2[vr * 2 + 2];
}
int xorusek1(int li, int ri, int vr)
{
    if (li > r[vr] || ri < l[vr])
    {
        return 0;
    }
    if (li <= l[vr] && ri >= r[vr])
    {
        return xor1[vr];
    }
    return xorusek1(li, ri, vr * 2 + 1) ^ xorusek1(li, ri, vr * 2 + 2);
}
int xorusek2(int li, int ri, int vr)
{
    if (li > r[vr] || ri < l[vr])
    {
        return 0;
    }
    if (li <= l[vr] && ri >= r[vr])
    {
        return xor2[vr];
    }
    return xorusek2(li, ri, vr * 2 + 1) ^ xorusek2(li, ri, vr * 2 + 2);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int q;
    cin >> q;
    vector<int>v(n);
    for (int i = maxn - 1; i < maxn * 2 - 1; i++)
    {
        l[i] = (i - maxn) + 1;
        r[i] = (i - maxn) + 1;
    }
    for (int i = maxn - 2; i >= 0; i--)
    {
        l[i] = l[i * 2 + 1];
        r[i] = r[i * 2 + 2];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        update(i, 0, v[i]);
    }
    while (q--)
    {
        int typ;
        cin >> typ;
        if (typ == 1)
        {
            int index;
            cin >> index;
            int hod;
            cin >> hod;
            index -= 1;
            update(index, 0, hod);
            v[index] = hod;
        }
        else if (typ == 2)
        {
            int lavy;
            cin >> lavy;
            int pravy;
            cin >> pravy;
            lavy -= 1;
            pravy -= 1;
            if(((pravy-lavy)+1)%2==0)
            {
                cout << 0 << '\n';
            }
            else if (pravy == lavy)
            {
                cout << v[lavy] << '\n';
            }
            else
            {
                if (lavy % 2 == 0)
                {
                    cout << xorusek1(lavy, pravy, 0) << '\n';
                }
                else if(lavy%2==1)
                {
                    cout << xorusek2(lavy, pravy, 0) << '\n';
                }
            }
        }
    }
    return 0;
    //std::cout << "Hello World!\n";
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started:
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file file

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4428 KB Output is correct
2 Correct 3 ms 4428 KB Output is correct
3 Correct 3 ms 4428 KB Output is correct
4 Correct 4 ms 4428 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 4 ms 4448 KB Output is correct
8 Correct 4 ms 4428 KB Output is correct
9 Correct 5 ms 4448 KB Output is correct
10 Correct 4 ms 4428 KB Output is correct
11 Correct 8 ms 4428 KB Output is correct
12 Correct 10 ms 4428 KB Output is correct
13 Correct 9 ms 4428 KB Output is correct
14 Correct 10 ms 4472 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 6268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4428 KB Output is correct
2 Correct 3 ms 4428 KB Output is correct
3 Correct 3 ms 4428 KB Output is correct
4 Correct 4 ms 4428 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 4 ms 4448 KB Output is correct
8 Correct 4 ms 4428 KB Output is correct
9 Correct 5 ms 4448 KB Output is correct
10 Correct 4 ms 4428 KB Output is correct
11 Correct 8 ms 4428 KB Output is correct
12 Correct 10 ms 4428 KB Output is correct
13 Correct 9 ms 4428 KB Output is correct
14 Correct 10 ms 4472 KB Output is correct
15 Incorrect 211 ms 6268 KB Output isn't correct
16 Halted 0 ms 0 KB -