oj.uz

Submission #466182

# Submission time Handle Problem Language Result Execution time Memory
466182 2021-08-18T10:39:55 Z Baray XORanges (eJOI19_xoranges) C++17
38 / 100
 723 ms 5252 KB 
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>

using namespace std;

#define ll long long
#define MOD 1000000007

int T = 1, n, q, oper, a, b, sum, temp;
vector<int> arr, odds, evens;
int segOdd[800000], segEven[800000];

void init(int cur, int l, int r, int ind) {
    if (l == r) {
        if (ind == 1) {
            segOdd[cur] = odds[l];
        }
        else {
            segEven[cur] = evens[l];
        }
        return;
    }

    init(cur * 2, l, (l + r) / 2, ind);
    init(cur * 2 + 1, (l + r) / 2 + 1, r, ind);

    if (ind == 1) {
        segOdd[cur] = segOdd[cur * 2] ^ segOdd[cur * 2 + 1];
    }
    else {
        segEven[cur] = segEven[cur * 2] ^ segEven[cur * 2 + 1];
    }
}

int find(int cur, int l, int r, int tl, int tr, int ind) {
    if (l > tr || r < tl) {
        return 0;
    }
    
    if (l >= tl && r <= tr) {
        if (ind == 1) {
            return segOdd[cur];
        }
        return segEven[cur];
    }

    int a1 = find(cur * 2, l, (r + l) / 2, tl, tr, ind);
    int a2 = find(cur * 2 + 1, (l + r) / 2 + 1, r, tl, tr, ind);
    
    return a1 ^ a2;
}

void change(int cur, int l, int r, int target, int val, int ind) {
    if (l > target || r < target) {
        return;
    }

    if (l == r && l == target) {
        if (ind == 1) {
            segOdd[cur] = val;
        }
        segEven[cur] = val;
        return;
    }

    change(cur * 2, l, (l + r) / 2, target, val, ind);
    change(cur * 2 + 1, (l + r) / 2 + 1, r, target, val, ind);

    if (ind == 1) {
        segOdd[cur] = segOdd[cur * 2] ^ segOdd[cur * 2 + 1];
    }   
    else {
        segEven[cur] = segEven[cur * 2] ^ segEven[cur * 2 + 1];
    }
}

void solve() {
    cin >> n >> q;

    //arr.push_back(-1);
    odds.push_back(-1);
    evens.push_back(-1);

    for (int i = 0; i < n; i++) {
        cin >> temp;
        arr.push_back(temp);

        if (!(i % 2)) {
            odds.push_back(temp);
        }
        else {
            evens.push_back(temp);
        }
    }

    init(1, 1, odds.size(), 1);
    init(1, 1, evens.size(), 2);

    for (int i = 0; i < q; i++) {
        cin >> oper >> a >> b;

        if (oper == 1) {
            if (a % 2 == 0) {
                change(1, 1, evens.size(), (a + 1) / 2, b, 2);
                continue;
            }
            change(1, 1, odds.size(), a / 2 + 1, b, 1);
        }
        else {
            if ((a - b + 1) % 2 == 0) {
                cout << "0\n";
                continue;
            }
            if (a % 2 == 1) {
                cout << find(1, 1, odds.size(), a / 2 + 1, b / 2 + 1, 1) << "\n";
            }
            else {
                cout << find(1, 1, evens.size(), (a + 1) / 2, (b + 1) / 2, 2) << "\n";
            }
        }
    }

}

int main() {
    //cin >> T;
    while (T--) {
        solve();
    }
}

Subtask #1
0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 5224 KB Output is correct
2 Correct 723 ms 5252 KB Output is correct
3 Correct 642 ms 5224 KB Output is correct
4 Correct 640 ms 5224 KB Output is correct
5 Correct 650 ms 5216 KB Output is correct

Subtask #5
0 / 25.0

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