제출 #1097511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097511		vjudge1	XORanges (eJOI19_xoranges)	C++11	0 / 100	93 ms	8528 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) ((S) & -(S))
/*
8 4
1 2 3 4 5 6 7 8
2 3 7
2 3 6
2 2 7
2 2 6
*/
/*

*/
//parece funcionar
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; cin >> n >> q;
    int n_odd = (n + 1) / 2, n_even = n / 2;
    while (__builtin_popcount(n_odd) > 1) n_odd += LSOne(n_odd);
    while (__builtin_popcount(n_even) > 1) n_even += LSOne(n_even);
    cout << n_odd << ' ' << n_even << '\n';
    vector<int> odd(2 * n_odd), even(2 * n_even);
    for (int i = 0; i < n; ++i) {
        if (i%2) {
            cin >> even[n_even + i/2];
        }else {
            cin >> odd[n_odd + i/2];
        }
    }
    for (int i = n_odd - 1; i > 0; --i) {
        odd[i] = odd[i * 2] ^ odd[i * 2 + 1];
    }
    for (int i = n_even - 1; i > 0; --i) {
        even[i] = even[i * 2] ^ even[i * 2 + 1];
    }
    // for (int i = 0; i < 2*n_odd; ++i) {
    //     cout << ' ' << odd[i];
    // }
    // cout << '\n';
    // for (int i = 0; i < 2*n_even; ++i) {
    //     cout << ' ' << even[i];
    // }
    // cout << endl;
    while (q--) {
        int accion; cin >> accion;
        if (accion == 1) { //rescan
            int i, j; cin >> i >> j; --i;
            if (i%2) {
                modificar(even[n_even + i/2] ^ j, even, 0, n_even - 1, 1, i/2);
            }else {
                modificar(odd[n_odd + i/2] ^ j, odd, 0, n_odd - 1, 1, i/2);
            }
            // for (int i = 0; i < 2*n_odd; ++i) {
            //     cout << ' ' << odd[i];
            // }
            // cout << '\n';
            // for (int i = 0; i < 2*n_even; ++i) {
            //     cout << ' ' << even[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%2) {
                if (l%2) {
                    // cout << "caso b" << endl;
                    cout << consultar(even, 1, 0, n_even - 1, l/2, u/2) << '\n';
                }else {
                    // cout << "caso a" << endl;
                    cout << consultar(odd, 1, 0, n_odd - 1, l/2, u/2) << '\n';
                }
            }else {
                cout << "0\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