oj.uz

Submission #448775

# Submission time Handle Problem Language Result Execution time Memory
448775 2021-08-01T13:03:06 Z UltraFalcon XORanges (eJOI19_xoranges) C++17
0 / 100
 293 ms 16404 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

struct Segtree{
    int n;
    vector<pair<int, int>> data;

    Segtree(const vector<int>& v) {
        n = v.size();
        data = vector<pair<int, int>>(4*n);
        build(v, 1, 0, n);
    }

    public:
    void set(int i, int x) {
        set(i, x, 1, 0, n);
    }

    int get(int beg, int ed) {
        return get(beg, ed, 1, 0, n).first;
    }

    private:
    pair<int, int> get_data(pair<int, int> left, pair<int, int> right, int ll) { // ll = left length
        //cerr << "{" << left.first << " | " << left.second << "}, {" << right.first << " | " << right.second << "}\n";
        //cerr << ll << "\n";
        if (ll <= 0) {
            return right;
        } else if (ll % 2 == 0) {
            return make_pair(left.first ^ right.first, left.second ^ right.second);
        } else {
            return make_pair(left.first ^ right.second, left.second ^ right.first);
        }
    }

    void update(int pos, int ll) {
        data[pos] = get_data(data[pos*2], data[pos*2+1], ll);
    }

    void build(const vector<int>& v, int pos, int left, int right) {
        if (left+1 == right) {
            data[pos] = make_pair(v[left], 0);
        } else {
            int mid = (left + right) / 2;
            build(v, pos*2, left, mid);
            build(v, pos*2+1, mid, right);
            update(pos, mid-left);
        }
    }

    void set(int i, int x, int pos, int left, int right) {
        if (left+1 == right) {
            data[pos] = make_pair(x, 0);
        } else {
            int mid = (left + right) / 2;
            if (i < mid) {
                set(i, x, pos*2, left, mid);
            } else {
                set(i, x, pos*2+1, mid, right);
            }
            update(pos, mid-left);
        }
    }

    pair<int, int> get(int beg, int ed, int pos, int left, int right) {
        if (beg <= left && ed >= right) {
            return data[pos];
        } else if (beg >= right || ed <= left) {
            return make_pair(0, 0);
        } else {
            int mid = (left + right) / 2;
            return get_data(get(beg, ed, pos*2, left, mid),
                            get(beg, ed, pos*2+1, mid, right),
                            mid-min(beg, mid));
        }
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }

    Segtree seg(a);

    for (int idx=0; idx<q; idx++) {
        int event;
        cin >> event;

        if (event == 1) {
            int i, j;
            cin >> i >> j;

            seg.set(i-1, j);
        } else {
            int l, u;
            cin >> l >> u;

            if ((l - u) % 2 == 1) {
                cout << 0 << "\n";
            } else {
                cout << seg.get(l-1, u) << "\n";
            }
        }
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 16404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -