oj.uz

Submission #639172

# Submission time Handle Problem Language Result Execution time Memory
639172 2022-09-08T19:44:39 Z shalekberli XORanges (eJOI19_xoranges) C++17
100 / 100
 171 ms 16108 KB 
/*
BY: shalekberli (Shahin Alekberli)
LANG: C++
*/
 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include<bits/stdc++.h>
//MACROS//
#define need_for_speed ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define _crt_secure_no_warnings
#define endl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define INF 0x3F3F3F3F
#define INFL 0x3F3F3F3F3F3F3F3FLL
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define UB upper_bound
#define LB lower_bound
#define F first
#define S second
#define mod 1000000007LL
#define MOD 998244353LL
#define MoD 16714589LL
#define moD 1000000LL;
#define Max 1e18
#define ll long long
#define lld long double
#define usi unsigned int
#define ull unsigned long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fix(n, k) fixed << setprecision((k)) << (n)
#define loop1(i, n, d) for (ll i = 1; i <= (n); i += (d))
#define loop0(i, n, d) for (ll i = 0; i < (n); i += (d))
#define loop(i, k, n, d) for(ll i = (k);i <= (n);i += (d))
#define loopr(i, k, n, d) for (ll i = (k); i >= (n); i -= (d))
#define read(x) for(auto &i: x) cin >> i
#define readi(x) for(int &i : x) cin >> i
#define readll(x) for(ll &i : x) cin >> i
#define readpii(x) for(pii &i : x) cin >> i
#define readpll(x) for(pll &i : x) cin >> i
#define write(x) for(auto &i: x) cout << i << " "
#define writend(x) for(auto &i: x) cout << i << endl
#define alphalower "abcdefghijklmnopqrstuvwxyz"
#define alphaupper "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
using namespace std;

const ll MAX = 200200;

ll sto[4 * MAX], ste[4 * MAX];
ll a[MAX];

void Build(ll v, ll l, ll r){
    if(l == r){
        if(l & 1) sto[v] = a[l];
        else ste[v] = a[l];
    }
    else{
        ll mid = (l + r) / 2;
        Build(2 * v, l, mid);
        Build(2 * v + 1, mid + 1, r);

        sto[v] = (sto[2 * v] ^ sto[2 * v + 1]);
        ste[v] = (ste[2 * v] ^ ste[2 * v + 1]);
    }
}

void Update(ll v, ll l, ll r, ll i, ll val){
    if(l == r){
        if(i & 1) sto[v] = val;
        else ste[v] = val;
    }
    else{
        ll mid = (l + r) / 2;
        if(i <= mid) Update(2 * v, l, mid, i, val);
        else Update(2 * v + 1, mid + 1, r, i, val);

        sto[v] = (sto[2 * v] ^ sto[2 * v + 1]);
        ste[v] = (ste[2 * v] ^ ste[2 * v + 1]);
    }
}

ll Xor(ll v, ll l, ll r, ll i, ll j, ll flag){
    if(i > j) return 0;
    if(l == i && r == j){
        if(flag) return sto[v];
        return ste[v];
    }
    ll mid = (l + r) / 2;
    return (Xor(2 * v, l, mid, i, min(mid, j), flag) ^ Xor(2 * v + 1, mid + 1, r, max(mid + 1, i), j, flag));
}

void solve(){
    int n, q; cin >> n >> q;
    loop1(i, n, 1) {
        cin >> a[i];
    }
    Build(1, 1, n);
    while(q--){
        int cm; cin >> cm;
        if(cm == 1){
            ll i, val; cin >> i >> val;
            Update(1, 1, n, i, val);
        }
        else{
            ll l, r; cin >> l >> r;
            if((r - l + 1) & 1){
                if(l & 1){
                    cout << Xor(1, 1, n, l, r, 1) << endl;
                }
                else{
                    cout << Xor(1, 1, n, l, r, 0) << endl;
                }
            }
            else{
                cout << 0 << endl;
            }
        }
    }
}

int main(){
    need_for_speed
    /* ll t; cin >> t;
    while(t--){
        solve();
    } */
    solve();
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 3 ms 696 KB Output is correct
13 Correct 3 ms 704 KB Output is correct
14 Correct 3 ms 724 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 16108 KB Output is correct
2 Correct 139 ms 16020 KB Output is correct
3 Correct 136 ms 16056 KB Output is correct
4 Correct 119 ms 15760 KB Output is correct
5 Correct 115 ms 15804 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 3 ms 696 KB Output is correct
13 Correct 3 ms 704 KB Output is correct
14 Correct 3 ms 724 KB Output is correct
15 Correct 171 ms 16108 KB Output is correct
16 Correct 139 ms 16020 KB Output is correct
17 Correct 136 ms 16056 KB Output is correct
18 Correct 119 ms 15760 KB Output is correct
19 Correct 115 ms 15804 KB Output is correct
20 Correct 131 ms 15888 KB Output is correct
21 Correct 135 ms 15812 KB Output is correct
22 Correct 123 ms 15872 KB Output is correct
23 Correct 113 ms 15812 KB Output is correct
24 Correct 126 ms 15700 KB Output is correct