oj.uz

Submission #844900

# Submission time Handle Problem Language Result Execution time Memory
844900 2023-09-06T08:09:12 Z fanwen XORanges (eJOI19_xoranges) C++17
100 / 100
 329 ms 13264 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

template < class T, T (*f) (T, T), T (*e) ()>
struct segment_tree {
    vector <T> tree;
    int n;

    void update(int u, T p) {
        u--;
        for(tree[u += n] += p; u >>= 1; ) {
            tree[u] = f(tree[u << 1], tree[u << 1 | 1]);
        }
    }

    void set(int u, T p) {
        u--;
        for (tree[u += n] = p; u >>= 1; ) {
            tree[u] = f(tree[u << 1], tree[u << 1 | 1]);
        }
    }

    T get(int p) {
        return tree[p += n - 1];
    }

    T get(int l, int r) {
        l--;
        T resl = e(), resr = e();
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) resl = f(resl, tree[l++]);
            if(r & 1) resr = f(tree[--r], resr);
        }
        return f(resl, resr);
    }

    segment_tree(int n = 0) : n(n), tree(n << 2 | 1) {
        fill(tree.begin(), tree.end(), 0);
    }
};

int merge(int x, int y) { return x ^ y; }
int e() { return 0; }

void you_make_it(void) {
    int n, q; cin >> n >> q;
    vector <int> a(n + 1);
    segment_tree <int, merge, e> it0(n), it1(n);
    FOR(i, 1, n) {
        cin >> a[i];
        (i & 1 ? it1 : it0).set(i, a[i]);
    }
    while(q--) {
        int op, l, r; cin >> op >> l >> r;
        if(op == 1) {
            (l & 1 ? it1 : it0).set(l, r);
        } else if(r - l & 1) cout << 0 << endl;
        else cout << (r & 1 ? it1 : it0).get(l, r) << endl;
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

xoranges.cpp: In function 'void you_make_it()':
xoranges.cpp:71:21: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   71 |         } else if(r - l & 1) cout << 0 << endl;
      |                   ~~^~~
xoranges.cpp: In instantiation of 'segment_tree<T, f, e>::segment_tree(int) [with T = int; T (* f)(T, T) = merge; T (* e)() = e]':
xoranges.cpp:62:39:   required from here
xoranges.cpp:21:9: warning: 'segment_tree<int, merge, e>::n' will be initialized after [-Wreorder]
   21 |     int n;
      |         ^
xoranges.cpp:20:16: warning:   'std::vector<int> segment_tree<int, merge, e>::tree' [-Wreorder]
   20 |     vector <T> tree;
      |                ^~~~
xoranges.cpp:51:5: warning:   when initialized here [-Wreorder]
   51 |     segment_tree(int n = 0) : n(n), tree(n << 2 | 1) {
      |     ^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 7 ms 604 KB Output is correct
14 Correct 7 ms 748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 13136 KB Output is correct
2 Correct 329 ms 13244 KB Output is correct
3 Correct 304 ms 13168 KB Output is correct
4 Correct 324 ms 13020 KB Output is correct
5 Correct 298 ms 13008 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 7 ms 604 KB Output is correct
14 Correct 7 ms 748 KB Output is correct
15 Correct 300 ms 13136 KB Output is correct
16 Correct 329 ms 13244 KB Output is correct
17 Correct 304 ms 13168 KB Output is correct
18 Correct 324 ms 13020 KB Output is correct
19 Correct 298 ms 13008 KB Output is correct
20 Correct 206 ms 13264 KB Output is correct
21 Correct 185 ms 13204 KB Output is correct
22 Correct 196 ms 12984 KB Output is correct
23 Correct 290 ms 12960 KB Output is correct
24 Correct 286 ms 12884 KB Output is correct