oj.uz

Submission #977240

# Submission time Handle Problem Language Result Execution time Memory
977240 2024-05-07T14:41:40 Z matsak XORanges (eJOI19_xoranges) C++14
100 / 100
 113 ms 8808 KB 
//__________Lernik in red is rising for me__________//
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
 
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//__________Dhola ha?__________//
#define pb push_back
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define no_ans cout << -1 <<'\n'
#define ll long long
#define ppb pop_back
#define checking cout << "OK" << endl
#define ld long double
#define all(v) (v).begin(), (v).end()
#define MP make_pair
#define PII pair <int, int>
#define lower lower_bound
#define upper upper_bound
#define endl '\n'
 
void setIO(string name = "") {
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);  
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
void fastIO(){
    ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0); 
}
 
const ll inf = 1e9, mod = 1e9 + 7, LOG = 32, inf64 = 1e18;;
 
void setPrecision(int x){
    if(x == 0){
        return;
    }
    cout.setf(ios::fixed);
    cout.precision(x);
    return;
}

const int N = 2e5 + 7;
int n, q, a[N];
PII tree[4 * N];

struct segtree{
    int size = 1;

    void init(){
        while(size < n){
            size <<= 1;
        }

        build(0, 1, size + 1);
    }

    void build(int x, int lx, int rx){
        if(rx == lx + 1){
            if(lx > n){
                tree[x] = MP(0, 0);
                return;
            }

            if(lx & 1){
                tree[x] = MP(0, a[lx]);
            }
            else{
                tree[x] = MP(a[lx], 0);
            }
            return;
        }

        int m = (lx + rx) / 2;
        build(2 * x + 1, lx, m);
        build(2 * x + 2, m, rx);

        tree[x].first = tree[2 * x + 1].first ^ tree[2 * x + 2].first;
        tree[x].second = tree[2 * x + 1].second ^ tree[2 * x + 2].second;
    }

    void set(int i, int v, int x, int lx, int rx){
        if(rx == lx + 1){
            if(lx & 1){
                tree[x] = MP(0, v);
            }
            else{
                tree[x] = MP(v, 0);
            }
            return;
        }

        int m = (lx + rx) / 2;
        if(i < m){
            set(i, v, 2 * x + 1, lx, m);
        }
        else{
            set(i, v, 2 * x + 2, m, rx);
        }

        tree[x].first = tree[2 * x + 1].first ^ tree[2 * x + 2].first;
        tree[x].second = tree[2 * x + 1].second ^ tree[2 * x + 2].second;
    }

    void set(int i, int v){
        set(i, v, 0, 1, size + 1);
    }

    PII get(int l, int r, int x, int lx, int rx){
        if(lx > r || l >= rx){
            return MP(0, 0);
        }
        if(l <= lx && rx - 1 <= r){
            return tree[x];
        }

        int m = (lx + rx) / 2;
        PII get1 = get(l, r, 2 * x + 1, lx, m), get2 = get(l, r, 2 * x + 2, m, rx);

        return MP(get1.first ^ get2.first, get1.second ^ get2.second);
    }

    PII get(int l, int r){
        return get(l, r, 0, 1, size + 1);
    }
};

segtree st;

void solve(){   
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    st.init();
    
    while(q--){
        int t, i, j;
        cin >> t >> i >> j;

        if(t == 1){
            st.set(i, j);
        }
        else{
            if(i % 2 != j % 2){
                cout << 0 << endl;
            }
            else{
                PII s = st.get(i, j);
                if(i & 1){
                    cout << s.second << endl;
                }
                else{
                    cout << s.first << endl;
                }
            }
        }

        /*for(int i = 0; i < 15; i++){
            cout << i << ") " << tree[i].first << ' ' << tree[i].second << endl;
        }*/
    }
}
 
int main(){
    setIO("");
    fastIO();
    setPrecision(2);
    
    int Tests = 1;
    //cin >> Tests;
 
    while(Tests--){
        solve();
    }
    return 0; 
}

Compilation message

xoranges.cpp: In function 'void setIO(std::string)':
xoranges.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xoranges.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 3 ms 2652 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 8552 KB Output is correct
2 Correct 93 ms 8604 KB Output is correct
3 Correct 93 ms 8808 KB Output is correct
4 Correct 82 ms 8528 KB Output is correct
5 Correct 82 ms 8532 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 3 ms 2652 KB Output is correct
15 Correct 113 ms 8552 KB Output is correct
16 Correct 93 ms 8604 KB Output is correct
17 Correct 93 ms 8808 KB Output is correct
18 Correct 82 ms 8528 KB Output is correct
19 Correct 82 ms 8532 KB Output is correct
20 Correct 92 ms 8040 KB Output is correct
21 Correct 93 ms 8036 KB Output is correct
22 Correct 88 ms 8020 KB Output is correct
23 Correct 83 ms 8392 KB Output is correct
24 Correct 85 ms 8468 KB Output is correct