oj.uz

Submission #543648

# Submission time Handle Problem Language Result Execution time Memory
543648 2022-03-31T07:15:46 Z tudor XORanges (eJOI19_xoranges) C++17
0 / 100
 1000 ms 4724 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 4724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -