oj.uz

Submission #459218

# Submission time Handle Problem Language Result Execution time Memory
459218 2021-08-08T10:45:26 Z shmad XORanges (eJOI19_xoranges) C++14
100 / 100
 285 ms 47008 KB 
    #include <bits/stdc++.h>
     
    #define nl '\n'
    #define pb push_back
    #define E exit(0)
    #define all(v) v.begin(), v.end()
    #define ff first
    #define ss second
    #define sz(s) (int)(s).size()
    #define ll long long
    #define int ll
    #define oioi ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define vt vector
     
    using namespace std;
    using pii = pair<int, int>;
    using vvi = vt< vt<int> >;
     
    const int N = 2e5 + 5;
    const int INF = 1e18 + 7;
    const int MOD = 1e9 + 7;
    const double eps = 1e-6;
    const int B = 800;
     
    vt<int> a(N);
    int n;
    vvi t(4 * N, vt<int> (2, 0));
     
    void build (int v = 1, int tl = 1, int tr = n) {
        if (tl == tr) {
            t[v][tl & 1] = a[tl];
            return;
        }
        int tm = tl + tr >> 1;
        build(v << 1, tl, tm);
        build(v << 1 | 1, tm + 1, tr);
        t[v][0] = (t[v << 1][0] ^ t[v << 1 | 1][0]);
        t[v][1] = (t[v << 1][1] ^ t[v << 1 | 1][1]);
    }
     
    void upd (int pos, int val, int v = 1, int tl = 1, int tr = n) {
        if (tl > pos || tr < pos) {
            return;
        }
        if (tl == tr && tl == pos) {
            t[v][pos & 1] = val;
            return;
        }
        int tm = tl + tr >> 1;
        upd(pos, val, v << 1, tl, tm);
        upd(pos, val, v << 1 | 1, tm + 1, tr);
        t[v][pos & 1] = (t[v << 1][pos & 1] ^ t[v << 1 | 1][pos & 1]);
    }
     
    int get (int l, int r, int check, int v = 1, int tl = 1, int tr = n) {
        if (tl > r || tr < l) {
            return 0;
        }
        if (tl >= l && tr <= r) {
            return t[v][check];
        }
        int tm = tl + tr >> 1;
        int a = get(l, r, check, v << 1, tl, tm);
        int b = get(l, r, check, v << 1 | 1, tm + 1, tr);
        return (a ^ b);
    }
     
    void solve () {
        int q;
        cin >> n >> q;
        for (int i = 1; i <= n; i++) cin >> a[i];
        build();
        while (q--) {
            int type;
            cin >> type;
            if (type == 1) {
                int pos, x;
                cin >> pos >> x;
                upd(pos, x);
            }
            if (type == 2) {
                int l, r;
                cin >> l >> r;
                if ((r - l + 1) & 1) cout << get(l, r, (l & 1)) << nl;
                else cout << "0\n";
            }
        }
        cout << nl;
    }
     
    int test = 1;
     
    signed main () {
    //	freopen(".in", "r", stdin);
    //	freopen(".out", "w", stdout);
    	oioi
    //	cin >> test; 
        while (test--) solve();
        return 0;
    }

Compilation message

xoranges.cpp: In function 'void build(long long int, long long int, long long int)':
xoranges.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
xoranges.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
xoranges.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
xoranges.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int, long long int)':
xoranges.cpp:62:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 45636 KB Output is correct
2 Correct 49 ms 45712 KB Output is correct
3 Correct 51 ms 45636 KB Output is correct
4 Correct 49 ms 45600 KB Output is correct
5 Correct 49 ms 45636 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 45696 KB Output is correct
2 Correct 54 ms 45716 KB Output is correct
3 Correct 49 ms 45808 KB Output is correct
4 Correct 55 ms 45712 KB Output is correct
5 Correct 51 ms 45728 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 45636 KB Output is correct
2 Correct 49 ms 45712 KB Output is correct
3 Correct 51 ms 45636 KB Output is correct
4 Correct 49 ms 45600 KB Output is correct
5 Correct 49 ms 45636 KB Output is correct
6 Correct 50 ms 45696 KB Output is correct
7 Correct 54 ms 45716 KB Output is correct
8 Correct 49 ms 45808 KB Output is correct
9 Correct 55 ms 45712 KB Output is correct
10 Correct 51 ms 45728 KB Output is correct
11 Correct 52 ms 45668 KB Output is correct
12 Correct 52 ms 45728 KB Output is correct
13 Correct 53 ms 45736 KB Output is correct
14 Correct 52 ms 45764 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 46808 KB Output is correct
2 Correct 262 ms 46788 KB Output is correct
3 Correct 277 ms 47008 KB Output is correct
4 Correct 190 ms 46896 KB Output is correct
5 Correct 193 ms 46876 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 45636 KB Output is correct
2 Correct 49 ms 45712 KB Output is correct
3 Correct 51 ms 45636 KB Output is correct
4 Correct 49 ms 45600 KB Output is correct
5 Correct 49 ms 45636 KB Output is correct
6 Correct 50 ms 45696 KB Output is correct
7 Correct 54 ms 45716 KB Output is correct
8 Correct 49 ms 45808 KB Output is correct
9 Correct 55 ms 45712 KB Output is correct
10 Correct 51 ms 45728 KB Output is correct
11 Correct 52 ms 45668 KB Output is correct
12 Correct 52 ms 45728 KB Output is correct
13 Correct 53 ms 45736 KB Output is correct
14 Correct 52 ms 45764 KB Output is correct
15 Correct 282 ms 46808 KB Output is correct
16 Correct 262 ms 46788 KB Output is correct
17 Correct 277 ms 47008 KB Output is correct
18 Correct 190 ms 46896 KB Output is correct
19 Correct 193 ms 46876 KB Output is correct
20 Correct 283 ms 46268 KB Output is correct
21 Correct 285 ms 46228 KB Output is correct
22 Correct 269 ms 46304 KB Output is correct
23 Correct 199 ms 46848 KB Output is correct
24 Correct 206 ms 46868 KB Output is correct