Submission #1219214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219214		theiulius	XORanges (eJOI19_xoranges)	C++20	100 / 100	228 ms	11384 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define ff first
#define ss second
#define pb push_back
int n, q;
int num;
const int N = 2e5+5, mod = 998244353;
 
int tree1[4*N], tree2[4*N];
 
void update1(int x, int l, int r, int pos, int val){ // pos da find const ari querize
    if (l == r){
        tree1[x] = val;
        return;
    }
 
    // orobiti dzebna
    int mid = (l + r) / 2;
    if (pos <= mid){ // marcxniv
        update1(2 * x, l, mid, pos, val);
    }else{
        update1(2 * x + 1, mid + 1, r, pos, val);
    }
 
    tree1[x] = tree1[2 * x] ^ tree1[2 * x + 1]; // tree[2x] da tree[2x + 1] ukve datvlili gveqneba recursiis gamo
}
 
int get1(int x, int l, int r, int tl, int tr){ // query const: tl, tr
    // if (tl > tr){
    //     return 0;
    // }
 
    if (tl <= l && r <= tr){
        return tree1[x];
    }
 
    int mid = (l + r) / 2;
    int ans = 0;
    if (tl <= mid){ // marcxniv
        ans ^= get1(2 * x, l, mid, tl, tr);
    }
    if (mid + 1 <= tr){ // marjvniv
        ans ^= get1(2 * x + 1, mid + 1, r, tl, tr);
    }
 
    return ans;
}

void update2(int x, int l, int r, int pos, int val){ // pos da find const ari querize
    if (l == r){
        tree2[x] = val;
        return;
    }
 
    // orobiti dzebna
    int mid = (l + r) / 2;
    if (pos <= mid){ // marcxniv
        update2(2 * x, l, mid, pos, val);
    }else{
        update2(2 * x + 1, mid + 1, r, pos, val);
    }
 
    tree2[x] = tree2[2 * x] ^ tree2[2 * x + 1]; // tree[2x] da tree[2x + 1] ukve datvlili gveqneba recursiis gamo
}
 
int get2(int x, int l, int r, int tl, int tr){ // query const: tl, tr
    // if (tl > tr){
    //     return 0;
    // }
 
    if (tl <= l && r <= tr){
        return tree2[x];
    }
 
    int mid = (l + r) / 2;
    int ans = 0;
    if (tl <= mid){ // marcxniv
        ans ^= get2(2 * x, l, mid, tl, tr);
    }
    if (mid + 1 <= tr){ // marjvniv
        ans ^= get2(2 * x + 1, mid + 1, r, tl, tr);
    }
 
    return ans;
}


main(){
    /*ifstream cin(".in");
    ofstream cout(".out");*/
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> q;
    int a[n] = {};
    for (int i = 0; i < n; i++){
        cin >> a[i];
        if (i % 2 == 0){
            update1(1, 1, n, i + 1, a[i]);
        }else{
            update2(1, 1, n, i + 1, a[i]);
        }
    }
    
    for (int k = 0; k < q; k++){
        cin >> num;
        if (num == 1){
            int i, x;
            cin >> i >> x;
            i--;
            if (i % 2){
                update2(1, 1, n, i + 1, x);
            }else{
                update1(1, 1, n, i + 1, x);
            }
        }else{
            int l, r;
            cin >> l >> r;
            l--; r--;
            if ((r - l + 1) % 2 == 0){
                cout << 0 << endl;
            }else{
                if (l % 2){
                    cout << get2(1, 1, n, l + 1, r + 1) << endl;
                }else{
                    cout << get1(1, 1, n, l + 1, r + 1) << endl;
                }
            }
        }
    }
}

Compilation message (stderr)

xoranges.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main(){
      | ^~~~

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