Submission #543648

#	Time	Username	Problem	Language	Result	Execution time	Memory
543648		tudor	XORanges (eJOI19_xoranges)	C++17	0 / 100	1092 ms	4724 KiB

xoranges

#include <iostream>

using namespace std;
const int nmax = 2e5;

int v[nmax + 1];
int n;

int aint[2][nmax + 10];

void update ( int p, int node, int st, int dr, int poz, int val ) {
    if ( st == dr ) {
        aint[p][node] ^= val;
        return;
    }
    int mij = ( st + dr ) / 2;
    if ( poz <= mij )
        update ( p, node + 1, st, mij, poz, val );
    else
        update ( p, node + 2 * ( mij - st + 1 ), mij + 1, dr, poz, val );

    aint[p][node] = aint[p][node + 1] ^ aint[p][node + 2 * ( mij - st + 1 )];
}

int query ( int p, int node, int st, int dr, int a, int b ) {
    if ( st == a && dr == b )
        return aint[p][node];
    int mij = ( st + dr ) / 2;
    /**
    [------]
    [--][--]
    **/
    if ( b <= mij )
        return query ( p, node + 1, st, mij, a, b );
    if ( a > mij )
        return query ( p, node + 2 * ( mij - st + 1 ), mij + 1, dr, a, b );
    return query ( p, node + 1, st, mij, a, st ) ^ query ( p, node + 2 * ( st - mij + 1 ), mij + 1, st, mij + 1, b );
}

int main() {
    int n, q, t, x, y;

    cin >> n >> q;

    for ( int i = 1; i <= n; i++ ) {
        cin >> v[i];
        update ( i % 2, 0, 1, ( n + 1 ) / 2, ( i + 1 ) / 2, v[i] );
    }
//    for ( int i = 1; i <= n; i += 2 )
  //      cout << query ( i % 2, ( i + 1 ) / 2 ) << ' ';
    for ( int i = 1; i <= q; i++ ) {
        cin >> t >> x >> y;
        if ( t == 1 ) {
            update ( x % 2, 0, 1, ( n + 1 ) / 2, ( x + 1 ) / 2, y ^ v[x] );
            v[x] = y;
        } else {
            if ( ( y - x + 1 ) % 2 == 0 )
                cout << 0 << '\n';
            else
                cout << query ( x % 2, 0, 1, ( n + 1 ) / 2, ( x + 1 ) / 2, ( y + 1 ) / 2  ) << '\n';
        }
    }

    return 0;
}

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