oj.uz

Submission #637320

# Submission time Handle Problem Language Result Execution time Memory
637320 2022-09-01T10:41:44 Z ksu2009en XORanges (eJOI19_xoranges) C++17
100 / 100
 521 ms 16192 KB 
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>

using namespace std;
typedef long long ll;

ll const dim = (ll)(2 * 1e5);

ll todd[4 * dim], teven[4 * dim];

ll a[dim];

void build(ll v, ll l, ll r){
    if(l == r){
        if(l % 2 != 0)
            todd[v] = a[l];
        else
            teven[v] = a[l];
        
        return;
    }
    
    ll mid = (l + r) >> 1;
    
    build(2 * v + 1, l, mid);
    build(2 * v + 2, mid + 1, r);
    
    todd[v] = (todd[2 * v + 1] xor todd[2 * v + 2]);
    teven[v] = (teven[2 * v + 1] xor teven[2 * v + 2]);
}

void update(ll v, ll l, ll r, ll pos, ll val){
    if(pos < l || pos > r)
        return;
    
    if(l == r){
        if(pos % 2 != 0)
            todd[v] = val;
        else
            teven[v] = val;
        
        return;
    }
    
    ll mid = (l + r) >> 1;
    
    update(2 * v + 1, l, mid, pos, val);
    update(2 * v + 2, mid + 1, r, pos, val);
    
    todd[v] = (todd[2 * v + 1] xor todd[2 * v + 2]);
    teven[v] = (teven[2 * v + 1] xor teven[2 * v + 2]);
}

ll query(ll v, ll l, ll r, ll ql, ll qr, bool ok){
    if(r < ql || qr < l)
        return 0;
    
    if(ql <= l && r <= qr){
        if(ok)
            return todd[v];
        return teven[v];
    }
    
    ll mid = (l + r) >> 1;
    
    return (query(2 * v + 1, l, mid, ql, qr, ok) xor query(2 * v + 2, mid + 1, r, ql, qr, ok));
}

int main(){
    ll n, q;
    cin >> n >> q;
    
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    build(1, 1, n);
    
    while(q--){
        ll type;
        cin >> type;
        
        if(type == 1){
            ll pos, val;
            cin >> pos >> val;
            
            a[pos] =  val;
            
            update(1, 1, n, pos, val);
        }
        else{
            ll l, r;
            cin >> l >> r;
            
            if((r - l + 1) % 2 == 0)
                cout << 0 << endl;
            else{
                if(l % 2 != 0){ // odd
                    cout << query(1, 1, n, l, r, true) << endl;
                }
                else{ // even
                    cout << query(1, 1, n, l, r, false) << endl;
                }
            }
        }
    }
     
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 9 ms 672 KB Output is correct
12 Correct 11 ms 596 KB Output is correct
13 Correct 12 ms 792 KB Output is correct
14 Correct 11 ms 596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 14192 KB Output is correct
2 Correct 518 ms 16192 KB Output is correct
3 Correct 521 ms 16172 KB Output is correct
4 Correct 467 ms 15820 KB Output is correct
5 Correct 477 ms 15876 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 9 ms 672 KB Output is correct
12 Correct 11 ms 596 KB Output is correct
13 Correct 12 ms 792 KB Output is correct
14 Correct 11 ms 596 KB Output is correct
15 Correct 496 ms 14192 KB Output is correct
16 Correct 518 ms 16192 KB Output is correct
17 Correct 521 ms 16172 KB Output is correct
18 Correct 467 ms 15820 KB Output is correct
19 Correct 477 ms 15876 KB Output is correct
20 Correct 405 ms 15832 KB Output is correct
21 Correct 403 ms 15888 KB Output is correct
22 Correct 402 ms 15960 KB Output is correct
23 Correct 511 ms 15896 KB Output is correct
24 Correct 475 ms 15732 KB Output is correct