oj.uz

Submission #981627

# Submission time Handle Problem Language Result Execution time Memory
981627 2024-05-13T11:50:22 Z DP_196 XORanges (eJOI19_xoranges) C++14
100 / 100
 117 ms 19628 KB 
#include <bits/stdc++.h>

#ifdef OP_DEBUG
    #include <algo/debug.h>
#else
    #define debug(...) 26
#endif

using namespace std;

#define int 	long long
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()
#define TcT     template <class T

const   int     MOD = (int)1e9 + 7, INF = (int)4e18 + 18;

TcT>            bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT>            bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

void solve();

int32_t main() {
    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
    int testcases = 1;

#define TC 0
    if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */

const int N = 2e5 + 5;

int n, q;
int a[N];
int pref[N][2];

struct SegmentTree {
    int node[4 * N + 7][2];

    void build(int type, int id = 1, int left = 1, int right = n) {
        if (left == right)
            return void(node[id][type] = pref[left][type]);
        
        int mid = (left + right) >> 1;
        build(type, id << 1, left, mid);
        build(type, id << 1 | 1, mid + 1, right);

        node[id][type] = node[id << 1][type] ^  node[id << 1 | 1][type];
    }

    void update(int type, int pos, int val, int id = 1, int left = 1, int right = n) {
        if (pos < left || right < pos)
            return;
        
        if (left == right) {
            node[id][type] ^= a[pos];
            a[pos] = val;
            node[id][type] ^= a[pos];
            return;
        }

        int mid = (left + right) >> 1;
        update(type, pos, val, id << 1, left, mid);
        update(type, pos, val, id << 1 | 1, mid + 1, right);

        node[id][type] = node[id << 1][type] ^ node[id << 1 | 1][type];
    }

    int get(int type, int l, int r, int id = 1, int left = 1, int right = n) {
        if (r < left || right < l)
            return 0;
        
        if (l <= left && right <= r)
            return node[id][type];
        
        int mid = (left + right) >> 1;
        int lc = get(type, l, r, id << 1, left, mid);
        int rc = get(type, l, r, id << 1 | 1, mid + 1, right);

        return (lc ^ rc);
    }
} st;

void solve() {
    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    
    for (int i = 1; i <= n; ++i) {
        pref[i][0] = pref[i - 1][0] ^ ((i & 1) ? 0 : a[i]);
        pref[i][1] = pref[i - 1][1] ^ ((i & 1) ? a[i] : 0);
    }

    st.build(0);
    st.build(1);

    for (int op; q--;) {
        cin >> op;

        if (op == 1) {
            int u, v; cin >> u >> v;

            st.update(u & 1, u, v);
        } else {
            int l, r; cin >> l >> r;

            if ((r - l + 1) % 2 == 0)
                cout << 0 << '\n';
            else
                cout << st.get(l & 1, l - 1, r) << '\n';
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 3 ms 4828 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 3 ms 4956 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 17236 KB Output is correct
2 Correct 100 ms 19628 KB Output is correct
3 Correct 107 ms 19328 KB Output is correct
4 Correct 90 ms 19088 KB Output is correct
5 Correct 85 ms 19028 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 3 ms 4828 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 3 ms 4956 KB Output is correct
15 Correct 102 ms 17236 KB Output is correct
16 Correct 100 ms 19628 KB Output is correct
17 Correct 107 ms 19328 KB Output is correct
18 Correct 90 ms 19088 KB Output is correct
19 Correct 85 ms 19028 KB Output is correct
20 Correct 98 ms 19204 KB Output is correct
21 Correct 117 ms 19280 KB Output is correct
22 Correct 104 ms 19284 KB Output is correct
23 Correct 88 ms 19024 KB Output is correct
24 Correct 91 ms 19028 KB Output is correct