oj.uz

Submission #892793

# Submission time Handle Problem Language Result Execution time Memory
892793 2023-12-26T01:18:18 Z noiaint XORanges (eJOI19_xoranges) C++17
100 / 100
 86 ms 10276 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, q;
int a[N];

struct fenw {
    int n;
    vector<int> bit;

    void init(int _n) {
        n = _n;
        bit.assign(n + 5, 0);
    }

    void update(int u, int c) {
        for (; u <= n; u += u & -u) bit[u] ^= c;
    }

    int get(int u) {
        int res = 0;
        for (; u > 0; u -= u & -u) res ^= bit[u];
        return res;
    }

    int get(int l, int r) {
        return get(r) ^ get(l - 1);
    }
} t[2];


void process() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    t[0].init(n);
    t[1].init(n);

    for (int i = 1; i <= n; ++i) t[i & 1].update(i, a[i]);

    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            t[x & 1].update(x, a[x]);
            a[x] = y;
            t[x & 1].update(x, a[x]);
        } else {
            if ((y - x + 1) & 1) cout << t[x & 1].get(x, y) << '\n';
            else cout << 0 << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    #ifdef LOCAL
//    freopen("input.txt", "r", stdin);
    #else
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    #endif

    int tc = 1;
    // cin >> tc;

    while (tc--) {
        process();
    }

    return 0;
}

/*

*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 484 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 484 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 2 ms 560 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 600 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 10068 KB Output is correct
2 Correct 68 ms 10208 KB Output is correct
3 Correct 68 ms 10276 KB Output is correct
4 Correct 64 ms 9844 KB Output is correct
5 Correct 64 ms 9856 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 484 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 2 ms 560 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 69 ms 10068 KB Output is correct
16 Correct 68 ms 10208 KB Output is correct
17 Correct 68 ms 10276 KB Output is correct
18 Correct 64 ms 9844 KB Output is correct
19 Correct 64 ms 9856 KB Output is correct
20 Correct 86 ms 9812 KB Output is correct
21 Correct 77 ms 9844 KB Output is correct
22 Correct 68 ms 10012 KB Output is correct
23 Correct 65 ms 10140 KB Output is correct
24 Correct 64 ms 9812 KB Output is correct