oj.uz

Submission #464096

# Submission time Handle Problem Language Result Execution time Memory
464096 2021-08-12T11:38:35 Z Sench2006 XORanges (eJOI19_xoranges) C++14
100 / 100
 226 ms 12556 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

#define f first
#define s second
#define mpr make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

#define FOR(i, a, b) for(auto i = a; i < b; i++)
#define FORD(i, a, b) for(auto i = a - 1; i >= b; i--)
#define trav(x, v) for(auto x : v)

#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fileio freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

// --------------- SOLUTION --------------- //

const int N = 200005;
int a[N];
ll t1[4 * N], t2[4 * N];
vector<int> vv;
 
void build(int tl, int tr, int v) {
    if (tl == tr) {
        t1[v] = a[tl];
    }
    else {
        int m = (tl + tr) / 2;
        build(tl, m, v * 2);
        build(m + 1, tr, v * 2 + 1);
        t1[v] = t1[v * 2] ^ t1[v * 2 + 1];
    }
}
 
void build1(int tl, int tr, int v) {
    if (tl == tr) {
        t2[v] = vv[tl];
    }
    else {
        int m = (tl + tr) / 2;
        build1(tl, m, v * 2);
        build1(m + 1, tr, v * 2 + 1);
        t2[v] = t2[v * 2] ^ t2[v * 2 + 1];
    }
}
 
void update(int tl, int tr, int pos, int new_val, int v) {
    if (tl == tr) {
        t1[v] = new_val;
    }
    else {
        int m = (tl + tr) / 2;
        if (pos <= m) {
            update(tl, m, pos, new_val, v * 2);
        }
        else {
            update(m + 1, tr, pos, new_val, v * 2 + 1);
        }
        t1[v] = t1[v * 2] ^ t1[v * 2 + 1];
    }
}
 
void update1(int tl, int tr,int pos, int new_val, int v) {
    if (tl == tr) {
        t2[v] = new_val;
    }
    else {
        int m = (tl + tr) / 2;
        if (pos <= m) {
            update1(tl, m, pos, new_val, v * 2);
        }
        else {
            update1(m + 1, tr, pos, new_val, v * 2 + 1);
        }
        t2[v] = t2[v * 2] ^ t2[v * 2 + 1];
    }
}
 
ll sum(int tl, int tr, int l, int r, int v) {
    if (l > r)
        return 0;
    if (l == tl && r == tr)
        return t1[v];
    int m = (tl + tr) / 2;
    return sum(tl, m, l, min(r, m), v * 2)
        ^ sum(m + 1, tr, max(l, m + 1), r, v * 2 + 1);
}
 
ll sum1(int tl, int tr, int l, int r, int v) {
    if (l > r)
        return 0;
    if (l == tl && r == tr)
        return t2[v];
    int m = (tl + tr) / 2;
    return sum1(tl, m, l, min(r, m), v * 2)
        ^ sum1(m + 1, tr, max(l, m + 1), r, v * 2 + 1);
}
 
void solve() {
    int n, q;
    cin >> n >> q;
    FOR(i, 0, n) {
        cin >> a[i];
    }
    FOR(i, 0, n) {
        if (i % 2 == 0) {
            vv.push_back(a[i]);
        }
        else {
            vv.push_back(0);
        }
    }
    build(0, n - 1, 1);
    build1(0, n - 1, 1);
    while (q--) {
        int id, l, r;
        cin >> id >> l >> r;
        l--, r--;
        if (id == 1) {
            update(0, n - 1, l, r + 1, 1);
            if (l % 2 == 0) {
                update1(0, n - 1, l, r + 1, 1);
            }
        }
        else {
            if ((r - l + 1) % 2 == 0) {
                cout << 0 << "\n";
            } else if (r - l + 1 == 1) {
                cout << sum(0, n - 1, l, r, 1) << "\n";
            } else {
                if (l % 2 == 0) {
                    cout << sum1(0, n - 1, l, r, 1) << "\n";
                }
                else {
                    cout << (sum(0, n - 1, l, r, 1) ^ sum1(0, n - 1, l, r, 1)) << "\n";
                }
            }
        }
    }
}

int main() {
    fastio;
    // fileio;
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 588 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 4 ms 684 KB Output is correct
14 Correct 4 ms 692 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 11400 KB Output is correct
2 Correct 216 ms 11496 KB Output is correct
3 Correct 226 ms 11416 KB Output is correct
4 Correct 177 ms 11340 KB Output is correct
5 Correct 168 ms 11344 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 588 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 4 ms 684 KB Output is correct
14 Correct 4 ms 692 KB Output is correct
15 Correct 203 ms 11400 KB Output is correct
16 Correct 216 ms 11496 KB Output is correct
17 Correct 226 ms 11416 KB Output is correct
18 Correct 177 ms 11340 KB Output is correct
19 Correct 168 ms 11344 KB Output is correct
20 Correct 188 ms 10788 KB Output is correct
21 Correct 203 ms 10816 KB Output is correct
22 Correct 192 ms 12088 KB Output is correct
23 Correct 174 ms 12556 KB Output is correct
24 Correct 174 ms 12532 KB Output is correct