oj.uz

Submission #791311

# Submission time Handle Problem Language Result Execution time Memory
791311 2023-07-24T01:16:25 Z kristo31 XORanges (eJOI19_xoranges) C++17
100 / 100
 88 ms 16124 KB 
#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

#define gc getchar_unlocked
#define pii pair<long long, long long>
using ll = long long;

const int maxN = 2e5 + 10, maxM = 1e5 + 10, MAX = 1e7;
const ll maxScore = 4294967295;
const ll mod = 998244353;
const double pi = acos(-1.0);
const double e = exp(1.0);
const ll naught = -100001;
const ll maxT = ceil(sqrt(maxN)) + 1;
const ll root = 15311432;
const ll root_1 = 469870224;
const ll root_pw = (1 << 23);
const int K = 19;

ll seg[4 * maxN][2], arr[maxN];

template <typename T> void fastInt(T& angka) {
    T kali = 1; angka = 0; char input = gc();
    while (!isdigit(input)) { if (input == '-') kali = -1; input = gc(); }
    while (isdigit(input)) angka = (angka << 3) + (angka << 1) + input - 48, input = gc();
    angka *= kali;
}

void fastStr(string& str) {
    str = "";
    char c = '0';
    while ((c = gc()) && (c != -1 && c != '\n' && c != '\t' && c != '\r')) {
        str += c;
    }
}

ll powMod(ll x, ll y, ll p){
    ll res = 1;
    x %= p;
    if(!x) return 0;
    while (y > 0){
        if (y & 1) res = ((res % p) * (x % p)) % p;
        y = y >> 1;
        x = ((x % p) * (x % p)) % p;
    }
    return res;
}

ll inverseMod(ll x, ll p){
    return powMod(x, p - 2, p);
}

void build(ll ind, ll l, ll r){
    if(l > r) return;
    if(l == r){
        seg[ind][l & 1] = arr[l];
        return;
    }
    ll mid = (l + r) / 2;
    build(2 * ind, l, mid);
    build(2 * ind + 1, mid + 1, r);
    seg[ind][0] = seg[2 * ind][0] ^ seg[2 * ind + 1][0];
    seg[ind][1] = seg[2 * ind][1] ^ seg[2 * ind + 1][1];
}

void upd(ll ind, ll l, ll r, ll i){
    if(l > r) return;
    if(r < i || i < l) return;
    if(l == r){
        assert(l == i);
        seg[ind][l & 1] = arr[l];
        return;
    }
    ll mid = (l + r) / 2;
    upd(2 * ind, l, mid, i);
    upd(2 * ind + 1, mid + 1, r, i);
    seg[ind][0] = seg[2 * ind][0] ^ seg[2 * ind + 1][0];
    seg[ind][1] = seg[2 * ind][1] ^ seg[2 * ind + 1][1];
}

ll query(ll ind, ll l, ll r, ll tl, ll tr, ll x){
    if(l > r) return 0;
    if(r < tl || tr < l) return 0;
    if(tl <= l && r <= tr) return seg[ind][x];
    ll mid = (l + r) / 2;
    return query(2 * ind, l, mid, tl, tr, x) ^ query(2 * ind + 1, mid + 1, r, tl, tr, x);
}

inline void solve(){
    ll n, q;
    fastInt(n); fastInt(q);
    for(int i = 1; i <= n; ++i) fastInt(arr[i]);
    build(1, 1, n);
    for(int i = 1; i <= q; ++i){
        ll typ; fastInt(typ);
        if(typ == 1){
            ll i, x;
            fastInt(i); fastInt(x);
            arr[i] = x;
            upd(1, 1, n, i);
        }else{
            ll l, r;
            fastInt(l); fastInt(r);
            if((r - l + 1) % 2 == 0) cout << "0\n";
            else cout << query(1, 1, n, l, r, l & 1) << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    auto beg = high_resolution_clock::now();
    int t; t = 1;
    while(t--) solve();
    auto en = high_resolution_clock::now();
    auto dur = duration_cast<microseconds>(en - beg);
    //cout << dur.count() << 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 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
18.0 / 18.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 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 344 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 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 728 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 728 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 16048 KB Output is correct
2 Correct 65 ms 16020 KB Output is correct
3 Correct 88 ms 16124 KB Output is correct
4 Correct 53 ms 15720 KB Output is correct
5 Correct 66 ms 15732 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 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 728 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 728 KB Output is correct
15 Correct 65 ms 16048 KB Output is correct
16 Correct 65 ms 16020 KB Output is correct
17 Correct 88 ms 16124 KB Output is correct
18 Correct 53 ms 15720 KB Output is correct
19 Correct 66 ms 15732 KB Output is correct
20 Correct 67 ms 15784 KB Output is correct
21 Correct 66 ms 15820 KB Output is correct
22 Correct 67 ms 15864 KB Output is correct
23 Correct 54 ms 15684 KB Output is correct
24 Correct 68 ms 15676 KB Output is correct