Submission #815552

#	Time	Username	Problem	Language	Result	Execution time	Memory
815552		EntityPlantt	XORanges (eJOI19_xoranges)	C++14	100 / 100	108 ms	7172 KiB

xoranges

#include <vector>
#include <cstdio>
#include <algorithm>
#include <math.h>
using namespace std;
class segment_tree {
    int n;
    vector <int> tree;
public:
    segment_tree(vector <int> &v) {
        n = 1 << int(ceil(log2(v.size())));
        tree.resize((n << 1) - 1, 0);
        copy(v.begin(), v.end(), tree.begin() + n - 1);
        for (int i = n - 2; i >= 0; i--) {
            tree[i] = tree[(i << 1) + 1] ^ tree[(i << 1) + 2];
        }
    }
    int size() { return n; }
    void set(int i, const int &val) {
        i += n - 1;
        tree[i] = val;
        while (i) {
            i = i - 1 >> 1;
            tree[i] = tree[(i << 1) + 1] ^ tree[(i << 1) + 2];
        }
    }
    int get(int l, int r, int node = 0, int cl = 0, int cr = -1) {
        if (cr < 0) cr = n - 1;
        if (cl == l && cr == r) return tree[node];
        if (cl > r || cr < l) return 0;
        return get(l, min(r, cl + cr >> 1), (node << 1) + 1, cl, cl + cr >> 1) ^ get(max(l - 1, cl + cr >> 1) + 1, r, (node << 1) + 2, (cl + cr >> 1) + 1, cr);
    }
};
int n, q, i, x;
vector <int> a, b;
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    a.resize(n, 0); b.resize(n, 0);
    for (i = 0; i < n; i++) {
        scanf("%d", &x);
        if (i & 1) a[i] = x; else b[i] = x;
    }
    segment_tree A(a), B(b);
    while (q--) {
        scanf("%d%d%d", &n, &i, &x);
        if (n == 1) {
            if (--i & 1) A.set(i, x);
            else B.set(i, x);
        }
        else {
            if (--x - --i & 1) printf("0\n");
            else printf("%d\n", i & 1 ? A.get(i, x) : B.get(i, x));
        }
    }
}

Compilation message (stderr)

xoranges.cpp: In member function 'void segment_tree::set(int, const int&)':
xoranges.cpp:23:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   23 |             i = i - 1 >> 1;
      |                 ~~^~~
xoranges.cpp: In member function 'int segment_tree::get(int, int, int, int, int)':
xoranges.cpp:31:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         return get(l, min(r, cl + cr >> 1), (node << 1) + 1, cl, cl + cr >> 1) ^ get(max(l - 1, cl + cr >> 1) + 1, r, (node << 1) + 2, (cl + cr >> 1) + 1, cr);
      |                              ~~~^~~~
xoranges.cpp:31:69: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         return get(l, min(r, cl + cr >> 1), (node << 1) + 1, cl, cl + cr >> 1) ^ get(max(l - 1, cl + cr >> 1) + 1, r, (node << 1) + 2, (cl + cr >> 1) + 1, cr);
      |                                                                  ~~~^~~~
xoranges.cpp:31:100: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         return get(l, min(r, cl + cr >> 1), (node << 1) + 1, cl, cl + cr >> 1) ^ get(max(l - 1, cl + cr >> 1) + 1, r, (node << 1) + 2, (cl + cr >> 1) + 1, cr);
      |                                                                                                 ~~~^~~~
xoranges.cpp:31:140: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         return get(l, min(r, cl + cr >> 1), (node << 1) + 1, cl, cl + cr >> 1) ^ get(max(l - 1, cl + cr >> 1) + 1, r, (node << 1) + 2, (cl + cr >> 1) + 1, cr);
      |                                                                                                                                         ~~~^~~~
xoranges.cpp: In function 'int main()':
xoranges.cpp:52:21: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   52 |             if (--x - --i & 1) printf("0\n");
      |                 ~~~~^~~~~
xoranges.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
xoranges.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
xoranges.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d%d%d", &n, &i, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25