Submission #1097495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097495		vjudge1	XORanges (eJOI19_xoranges)	C++11	0 / 100	156 ms	9296 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) ((S) & -(S))
void modificar(const int &v, vector<int> &a, const int &l, const int &r, const int &i, const int &j) {
    // cout << "modificar l=" << l << ", r=" << r << endl;
    if (l > j || r < j) return;
    // cout << "\tmodificado" << endl;
    a[i] ^= v;
    if (l >= r) return;
    // cout << "\tno es hoja" << endl;
    modificar(v, a, l,                  l + (r - l + 1)/2 - 1,  2*i,        j);
    modificar(v, a, l + (r - l + 1)/2,  r,                      2*i + 1,    j);
}
int consultar(const vector<int> &a, const int &x, const int &l, const int &r, const int &i, const int &j) {
    if (l > j || r < i) {
        return 0;
    }
    if (l >= i && r <= j) {
        return a[x];
    }
    return consultar(a, 2*x, l, l + (r - l + 1)/2 - 1, i, j) ^ consultar(a, 2*x + 1, l + (r - l + 1)/2, r, i, j);
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q, siz; cin >> n >> q;
    siz = n;
    while (__builtin_popcount(siz) > 1) siz -= LSOne(siz);
    siz *= 2;
    vector<int> a(siz), b(siz);
    for (int i = 0; i < n; ++i) {
        if (i%2) {
            cin >> b[siz/2 + i/2];
        }else {
            cin >> a[siz/2 + i/2];
        }
    }
    for (int i = siz/2 - 1; i > 0; --i) {
        a[i] = a[i*2] ^ a[i*2 + 1];
        b[i] = b[i*2] ^ b[i*2 + 1];
    }
    // for (int i = 0; i < siz; ++i) {
    //     cout << ' ' << a[i];
    // }
    // cout << '\n';
    // for (int i = 0; i < siz; ++i) {
    //     cout << ' ' << b[i];
    // }
    // cout << endl;
    while (q--) {
        int accion; cin >> accion;
        if (accion == 1) { //rescan
            int i, j; cin >> i >> j; --i;
            if (i%2) {
                modificar(b[siz/2 + i/2] ^ j, b, 0, siz/2 - 1, 1, i/2);
            }else {
                modificar(a[siz/2 + i/2] ^ j, a, 0, siz/2 - 1, 1, i/2);
            }
            // for (int i = 0; i < siz; ++i) {
            //     cout << ' ' << a[i];
            // }
            // cout << '\n';
            // for (int i = 0; i < siz; ++i) {
            //     cout << ' ' << b[i];
            // }
            // cout << endl;
        }else { //query
            int l, u; cin >> l >> u; --l; --u;
            int n_elem = u - l + 1;
            // cout << n_elem << endl;
            if ((n_elem + l)%2) {
                // cout << "caso a" << endl;
                cout << consultar(a, 1, 0, siz/2 - 1, l/2, u/2) << '\n';
            }else {
                // cout << "caso b" << endl;
                cout << consultar(b, 1, 0, siz/2 - 1, l/2, u/2) << '\n';
            }
        }
    }
    cout.flush();
    return EXIT_SUCCESS;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25