oj.uz

Submission #237704

# Submission time Handle Problem Language Result Execution time Memory
237704 2020-06-08T11:32:02 Z RiscadoA XORanges (eJOI19_xoranges) C++14
100 / 100
 541 ms 8696 KB 
#include <bits/stdc++.h>

using namespace std;

int N, Q, A[200000];

class Tree {
public:
    void init(int offset) {
        this->offset = offset;
        if (N % 2 != 0) {
            this->sz = N / 2 + 1 - this->offset;    
        } else {
            this->sz = N / 2;
        }

        this->build(0, 0, this->sz - 1);
    }

    void update(int i, int value) {
        this->internal_update(i, value, 0, 0, this->sz - 1);
    }

    int query(int l, int r) {
        return this->internal_query(l, r, 0, 0, this->sz - 1);
    }

private:
    int build(int ni, int nl, int nr) {
        if (nl == nr) {
            this->data[ni] = A[2 * nl + this->offset];
        } else {
            int mid = nl + (nr - nl) / 2;
            this->data[ni] =
                this->build(2 * ni + 1, nl, mid) ^
                this->build(2 * ni + 2, mid + 1, nr);
        }

        return this->data[ni];
    }

    int internal_update(int i, int value, int ni, int nl, int nr) {
        if (nl > i || nr < i) {
            return this->data[ni];
        } else if (nl == nr) {
            this->data[ni] = value;
        } else {
            int mid = nl + (nr - nl) / 2;
            this->data[ni] =
                this->internal_update(i, value, 2 * ni + 1, nl, mid) ^
                this->internal_update(i, value, 2 * ni + 2, mid + 1, nr);
        }

        return this->data[ni];
    }

    int internal_query(int l, int r, int ni, int nl, int nr) {
        if (nl > r || nr < l) {
            return 0;
        } else if (nl >= l && nr <= r) {
            return this->data[ni];
        } else {
            int mid = nl + (nr - nl) / 2;
            return
                this->internal_query(l, r, 2 * ni + 1, nl, mid) ^
                this->internal_query(l, r, 2 * ni + 2, mid + 1, nr);
        }
    }

    int sz, offset;
    int data[4 * 100000];
};

Tree tree[2];

void rescan(int i, int j) {
    tree[i % 2].update(i / 2, j);
}

int query(int l, int u) {
    if ((u - l + 1) % 2 == 0) {
        return 0;
    }

    return tree[l % 2].query(l / 2, u / 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> Q;

    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    for (int i = 0; i < 2; ++i) {
        tree[i].init(i);
    }

    for (int Qi = 0, action; Qi < Q; ++Qi) {
        cin >> action;
        if (action == 1) {
            int i, j;
            cin >> i >> j;
            rescan(i - 1, j);
        } else if (action == 2) {
            int l, u;
            cin >> l >> u;
            cout << query(l - 1, u - 1) << endl;
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 17 ms 512 KB Output is correct
12 Correct 13 ms 512 KB Output is correct
13 Correct 16 ms 564 KB Output is correct
14 Correct 16 ms 512 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 8696 KB Output is correct
2 Correct 537 ms 8544 KB Output is correct
3 Correct 541 ms 8624 KB Output is correct
4 Correct 494 ms 8572 KB Output is correct
5 Correct 515 ms 8568 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 17 ms 512 KB Output is correct
12 Correct 13 ms 512 KB Output is correct
13 Correct 16 ms 564 KB Output is correct
14 Correct 16 ms 512 KB Output is correct
15 Correct 529 ms 8696 KB Output is correct
16 Correct 537 ms 8544 KB Output is correct
17 Correct 541 ms 8624 KB Output is correct
18 Correct 494 ms 8572 KB Output is correct
19 Correct 515 ms 8568 KB Output is correct
20 Correct 328 ms 7928 KB Output is correct
21 Correct 338 ms 7928 KB Output is correct
22 Correct 348 ms 7928 KB Output is correct
23 Correct 477 ms 8684 KB Output is correct
24 Correct 491 ms 8528 KB Output is correct