oj.uz

Submission #445622

# Submission time Handle Problem Language Result Execution time Memory
445622 2021-07-19T05:16:22 Z aris12345678 XORanges (eJOI19_xoranges) C++14
100 / 100
 143 ms 8356 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 2*1e5+5;
int a[mxN];

template<typename T> struct Fenwick_Tree {
    vector<T> bit;
    void init(int n) {
        bit.assign(mxN, 0);
    }
    void update(int pos, T val, int n) {
        while(pos < mxN) {
            bit[pos] ^= val;
            pos += (pos&(-pos));
        }
    }
    T query(int pos) {
        int ans = 0;
        while(pos > 0) {
            ans ^= bit[pos];
            pos -= (pos&(-pos));
        }
        return ans;
    }
};

Fenwick_Tree<int> bit_even, bit_odd; 

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    bit_even.init(n);
    bit_odd.init(n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(i%2 == 0)
            bit_even.update(i, a[i], n);
        else
            bit_odd.update(i, a[i], n);
    }
    while(q--) {
        int type, l, r;
        scanf("%d %d %d", &type, &l, &r);
        if(type == 1) {
            if(l%2 == 0) {
                bit_even.update(l, a[l], n);
                bit_even.update(l, r, n);
            } else {
                bit_odd.update(l, a[l], n);
                bit_odd.update(l, r, n);
            }
            a[l] = r;
        } else {
            if(l%2 != r%2)
                printf("0\n");
            else {
                int ans;
                if(l == 1) {
                    if(r%2 == 0)
                        ans = bit_even.query(r);
                    else
                        ans = bit_odd.query(r);
                } else {
                    if(r%2 == 0)
                        ans = bit_even.query(r)^bit_even.query(l-1);
                    else
                        ans = bit_odd.query(r)^bit_odd.query(l-1);
                }
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

Compilation message

xoranges.cpp: In function 'int main()':
xoranges.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
xoranges.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
xoranges.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d %d %d", &type, &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 2 ms 1868 KB Output is correct
8 Correct 2 ms 1868 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 2 ms 1868 KB Output is correct
11 Correct 4 ms 1996 KB Output is correct
12 Correct 4 ms 2040 KB Output is correct
13 Correct 5 ms 1996 KB Output is correct
14 Correct 4 ms 1996 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 4824 KB Output is correct
2 Correct 130 ms 4840 KB Output is correct
3 Correct 143 ms 4824 KB Output is correct
4 Correct 127 ms 4796 KB Output is correct
5 Correct 139 ms 4836 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 2 ms 1868 KB Output is correct
8 Correct 2 ms 1868 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 2 ms 1868 KB Output is correct
11 Correct 4 ms 1996 KB Output is correct
12 Correct 4 ms 2040 KB Output is correct
13 Correct 5 ms 1996 KB Output is correct
14 Correct 4 ms 1996 KB Output is correct
15 Correct 133 ms 4824 KB Output is correct
16 Correct 130 ms 4840 KB Output is correct
17 Correct 143 ms 4824 KB Output is correct
18 Correct 127 ms 4796 KB Output is correct
19 Correct 139 ms 4836 KB Output is correct
20 Correct 129 ms 7076 KB Output is correct
21 Correct 132 ms 8348 KB Output is correct
22 Correct 125 ms 8320 KB Output is correct
23 Correct 114 ms 8356 KB Output is correct
24 Correct 136 ms 8328 KB Output is correct