oj.uz

Submission #637319

# Submission time Handle Problem Language Result Execution time Memory
637319 2022-09-01T10:40:59 Z ksu2009en XORanges (eJOI19_xoranges) C++17
55 / 100
 91 ms 5808 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[dim], teven[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 340 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 312 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 312 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 9 ms 724 KB Output is correct
12 Correct 9 ms 708 KB Output is correct
13 Correct 12 ms 724 KB Output is correct
14 Correct 12 ms 704 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 5808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 312 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 9 ms 724 KB Output is correct
12 Correct 9 ms 708 KB Output is correct
13 Correct 12 ms 724 KB Output is correct
14 Correct 12 ms 704 KB Output is correct
15 Runtime error 91 ms 5808 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -