oj.uz

Submission #951822

# Submission time Handle Problem Language Result Execution time Memory
951822 2024-03-22T17:45:27 Z EJIC_B_KEDAX XORanges (eJOI19_xoranges) C++17
100 / 100
 111 ms 13616 KB 
#include <bits/stdc++.h>

#include <random>
#ifndef LOCAL
//#pragma GCC optimize("O3")
    //#pragma GCC optimize("Ofast")
    //#pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
typedef long long ll;
typedef double dd;
typedef long double ld;
typedef unsigned int uii;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

void solve();

mt19937_64 mt(1);

int32_t main() {
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //freopen("amusing.in", "r", stdin);
    //freopen("amusing.out", "w", stdout);
#endif
    cout << fixed << setprecision(30);
    int tests = 1;
    //cin >> tests;
    while (tests--) {
        solve();
    }
}

struct point {
    uii x;
    int l, r;
};

struct SegmentTree {
    vector<point> st;
    int sz;
    explicit SegmentTree(vector<int>& a) {
        int n = a.size();
        int i2 = 1;
        while (i2 < n) {
            i2 <<= 1;
        }
        sz = i2;
        st.resize(2 * i2 - 1);
        for (int i = i2 - 1; i < 2 * i2 - 1; i++) {
            if (i - i2 + 1 < n) {
                st[i].x = a[i - i2 + 1];
            } else {
                st[i].x = 0;
            }
            st[i].l = i - i2 + 1;
            st[i].r = i - i2 + 1;
        }
        for (int i = i2 - 2; i >= 0; i--) {
            st[i] = {st[2 * i + 1].x ^ st[2 * i + 2].x, st[2 * i + 1].l, st[2 * i + 2].r};
        }
    }
    void update(int i, uii c) {
        i += sz - 1;
        uii d = st[i].x ^ c;
        while (i) {
            st[i].x ^= d;
            i = (i - 1) / 2;
        }
        st[i].x ^= d;
    }
    uii get(int l, int r, int i = 0) {
        if (st[i].l > r || st[i].r < l) {
            return 0;
        }
        if (st[i].l >= l && st[i].r <= r) {
            return st[i].x;
        }
        return get(l, r, 2 * i + 1) ^ get(l, r, 2 * i + 2);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a1, a2;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (i % 2) {
            a2.push_back(x);
        } else {
            a1.push_back(x);
        }
    }
    SegmentTree st1(a1), st2(a2);
    while (q--) {
        int c;
        cin >> c;
        if (c == 1) {
            int i, x;
            cin >> i >> x; i--;
            if (i % 2) {
                st2.update(i / 2, x);
            } else {
                st1.update(i / 2, x);
            }
        } else {
            int l, r;
            cin >> l >> r; l--; r--;
            if ((r - l) % 2) {
                cout << "0\n";
            } else {
                if (l % 2) {
                    cout << st2.get(l / 2, r / 2) << '\n';
                } else {
                    cout << st1.get(l / 2, r / 2) << '\n';
                }
            }
        }
    }
}

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 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 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 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 3 ms 600 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 99 ms 13500 KB Output is correct
2 Correct 98 ms 13508 KB Output is correct
3 Correct 111 ms 13616 KB Output is correct
4 Correct 85 ms 13120 KB Output is correct
5 Correct 84 ms 13256 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 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 3 ms 600 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 99 ms 13500 KB Output is correct
16 Correct 98 ms 13508 KB Output is correct
17 Correct 111 ms 13616 KB Output is correct
18 Correct 85 ms 13120 KB Output is correct
19 Correct 84 ms 13256 KB Output is correct
20 Correct 83 ms 13304 KB Output is correct
21 Correct 81 ms 13252 KB Output is correct
22 Correct 82 ms 13256 KB Output is correct
23 Correct 86 ms 13316 KB Output is correct
24 Correct 82 ms 13252 KB Output is correct