oj.uz

Submission #684186

# Submission time Handle Problem Language Result Execution time Memory
684186 2023-01-20T15:37:27 Z Tigerpants XORanges (eJOI19_xoranges) C++17
100 / 100
 214 ms 32976 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <string>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

#define rep(x, a, b) for (ll x = a; x < b; x++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define sz(a) a.size()
#define resz(a, n) a.resize(n)

vll oranges;
vpll segtree;
vpll interval;

pll combine(pll x, pll y) {
    return mp(x.first ^ y.first, x.second ^ y.second);
}

pll segtree_assign(ll val, int pos) {
    if (pos & 1) {
        return mp(val, 0);
    } else {
        return mp(0, val);
    }
}

void build(int cur, int l, int r) {
    interval[cur] = mp(l, r);
    if (l == r) {
        segtree[cur] = segtree_assign(oranges[l], l);
        return;
    }
    int m = (l + r) / 2;
    build(2 * cur, l, m);
    build(2 * cur + 1, m + 1, r);
    segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}

pll query(int cur, int l, int r) {
    if ((interval[cur].first > r) || (interval[cur].second < l)) {
        return mp(0, 0);
    }
    if ((l <= interval[cur].first) && (interval[cur].second <= r)) {
        return segtree[cur];
    }
    return combine(query(2 * cur, l, r), query(2 * cur + 1, l, r));
}

void update(int cur, int x, ll val) {
    if ((interval[cur].first > x) || (x > interval[cur].second)) {
        return;
    }
    if (interval[cur].first == interval[cur].second) {
        segtree[cur] = segtree_assign(val, x);
        return;
    }
    update(2 * cur, x, val);
    update(2 * cur + 1, x, val);
    segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, q;
    cin >> n >> q;

    resz(oranges, n);
    resz(segtree, 4 * n);
    resz(interval, 4 * n);
    rep(i, 0, n) {
        cin >> oranges[i];
    }
    build(1, 0, n - 1);

    /*
    rep(i, 0, 2 * n) {
        cout << "(" << segtree[i].first << ", " << segtree[i].second << ") ";
    }
    cout << endl;
    */

    ll tmpa, tmpb, tmpc;
    rep(i, 0, q) {
        cin >> tmpa >> tmpb >> tmpc;
        if (tmpa == 1) {
            update(1, tmpb - 1, tmpc);
        } else {
            if ((tmpc + tmpb) & 1) {
                cout << "0\n";
            } else {
                // odd length
                pll res = query(1, tmpb - 1, tmpc - 1);
                //cout << "(" << res.first << ", " << res.second << ")" << endl;
                if (tmpb & 1) {
                    // take even indexed, which is res.second
                    cout << res.second << "\n";
                } else {
                    cout << res.first << "\n";
                }
            }
        }
        /*
        rep(i, 0, 2 * n) {
            cout << "(" << segtree[i].first << ", " << segtree[i].second << ") ";
        }
        cout << endl;
        */
    }

    return 0;
}

// for a range: find xor of all elements, all pairs of consequtive, all triplets of consequtive, etc...
// so for x in [l, r] we want to find if this coordinate contributes or not...
// the number of ranges which include x is:
// (x - l + 1) * (r - x + 1)
// when (l - 1) + (r + 1) = r - l is odd, this number ^^ is always even so answer is 0
// when r - l is even, then x=l, l + 2, l + 4, ..., r - 2, r contribute to answer
// so we have 2 segment-trees, for even and odd

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 4 ms 1108 KB Output is correct
13 Correct 3 ms 1104 KB Output is correct
14 Correct 4 ms 1108 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 30752 KB Output is correct
2 Correct 175 ms 32976 KB Output is correct
3 Correct 161 ms 32972 KB Output is correct
4 Correct 117 ms 32652 KB Output is correct
5 Correct 120 ms 32716 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 4 ms 1108 KB Output is correct
13 Correct 3 ms 1104 KB Output is correct
14 Correct 4 ms 1108 KB Output is correct
15 Correct 168 ms 30752 KB Output is correct
16 Correct 175 ms 32976 KB Output is correct
17 Correct 161 ms 32972 KB Output is correct
18 Correct 117 ms 32652 KB Output is correct
19 Correct 120 ms 32716 KB Output is correct
20 Correct 214 ms 32680 KB Output is correct
21 Correct 178 ms 32712 KB Output is correct
22 Correct 177 ms 32620 KB Output is correct
23 Correct 125 ms 32556 KB Output is correct
24 Correct 121 ms 32592 KB Output is correct