Submission #466182

#	Time	Username	Problem	Language	Result	Execution time	Memory
466182		Baray	XORanges (eJOI19_xoranges)	C++17	38 / 100	723 ms	5252 KiB

xoranges

#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
• Subtask 2: 18 / 18
• Subtask 3: 0 / 25
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25