oj.uz

Submission #466194

# Submission time Handle Problem Language Result Execution time Memory
466194 2021-08-18T10:55:27 Z Baray XORanges (eJOI19_xoranges) C++17
100 / 100
 685 ms 5336 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;
            return;
        }
        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
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 2 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 2 ms 204 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 12 ms 476 KB Output is correct
12 Correct 12 ms 472 KB Output is correct
13 Correct 15 ms 472 KB Output is correct
14 Correct 15 ms 488 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 5184 KB Output is correct
2 Correct 656 ms 5220 KB Output is correct
3 Correct 650 ms 5224 KB Output is correct
4 Correct 613 ms 5268 KB Output is correct
5 Correct 628 ms 5232 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 12 ms 476 KB Output is correct
12 Correct 12 ms 472 KB Output is correct
13 Correct 15 ms 472 KB Output is correct
14 Correct 15 ms 488 KB Output is correct
15 Correct 685 ms 5184 KB Output is correct
16 Correct 656 ms 5220 KB Output is correct
17 Correct 650 ms 5224 KB Output is correct
18 Correct 613 ms 5268 KB Output is correct
19 Correct 628 ms 5232 KB Output is correct
20 Correct 496 ms 4636 KB Output is correct
21 Correct 501 ms 4616 KB Output is correct
22 Correct 504 ms 4616 KB Output is correct
23 Correct 624 ms 5084 KB Output is correct
24 Correct 624 ms 5336 KB Output is correct