oj.uz

Submission #464095

# Submission time Handle Problem Language Result Execution time Memory
464095 2021-08-12T11:37:15 Z Sench2006 XORanges (eJOI19_xoranges) C++14
75 / 100
 223 ms 12736 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 << a[l] << "\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 0 ms 332 KB Output is correct
2 Correct 0 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 332 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 0 ms 332 KB Output is correct
2 Correct 0 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 332 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 4 ms 588 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 6 ms 588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 11528 KB Output is correct
2 Correct 206 ms 12608 KB Output is correct
3 Correct 218 ms 12588 KB Output is correct
4 Correct 174 ms 12736 KB Output is correct
5 Correct 171 ms 12696 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 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 332 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 4 ms 588 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 6 ms 588 KB Output is correct
15 Correct 209 ms 11528 KB Output is correct
16 Correct 206 ms 12608 KB Output is correct
17 Correct 218 ms 12588 KB Output is correct
18 Correct 174 ms 12736 KB Output is correct
19 Correct 171 ms 12696 KB Output is correct
20 Correct 195 ms 12048 KB Output is correct
21 Incorrect 223 ms 12192 KB Output isn't correct
22 Halted 0 ms 0 KB -