oj.uz

Submission #462379

# Submission time Handle Problem Language Result Execution time Memory
462379 2021-08-10T12:45:22 Z gesgha XORanges (eJOI19_xoranges) C++17
100 / 100
 577 ms 14684 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fr(x, l, r) for(int x = l; x <= r; x++)
#define rf(x, l, r) for(int x = l; x >= r; x--)
#define fe(x, y) for(auto& x : y)

#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define pw(x) (ull(1) << ull(x))
#define all(x) (x).begin(),x.end()
#define sz(x) (int)x.size()
#define mt make_tuple
#define ve vector

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <ld,ld> pld;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template<typename T>
bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T>
bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; }

const ll inf = 1e18;
const int intf = 1e9;
const ll mod = 1e9 + 7;
const ld eps = 0.00000001;
const ll N  = 2e5 + 5;
const int TP = 2;

ll t[TP][4*N];


void modify(int tp, int pos, int tl, int tr, int v, int val){
    if(tl == tr){
        t[tp][v] = val;
        return;
    }

    int m = (tl + tr) / 2;

    if(pos <= m) modify(tp, pos, tl, m, v*2, val);
    else modify (tp, pos, m + 1, tr, v * 2 + 1, val);
    t[tp][v] = t[tp][v*2]^t[tp][v * 2 + 1];
}


int get(int tp, int l, int r, int tl, int tr, int v){

    if(l > r)return 0;


    if(l == tl && tr == r){
        return t[tp][v];
    }

    int m = (tl + tr)/2;

    return (get(tp, l, min(m, r), tl, m, v*2)^get(tp,max(l, m + 1), r,m + 1, tr, v*2 + 1));
}


int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt","w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#else
//    freopen("mountains.in", "r", stdin);
//    freopen("mountains.out","w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif

    int n, q;
    cin >> n >> q;

    fr(i, 0, n - 1){
        int a;
        cin >> a;
        modify((i + 1)%2, i, 0, n - 1,1, a);
    }

    while(q--){
        int tp;
        cin >> tp;
        if(tp == 1){
            int a, pos;
            cin >> pos >> a;
            pos--;
            modify((pos + 1)%2,pos,0,n - 1,1,a);
        }
        else{
            int l, r;
            cin >> l >> r;
            l--;r--;
            int len = r - l + 1;
            if(len%2 == 0){
                cout << 0 << endl;
                continue;
            }
            int t = (l + 1)%2;
//            cout << "t = " << t << endl;
            cout << get(t, l, r,0,n - 1, 1) << endl;
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 9756 KB Output is correct
2 Correct 520 ms 14684 KB Output is correct
3 Correct 543 ms 14440 KB Output is correct
4 Correct 507 ms 14128 KB Output is correct
5 Correct 492 ms 14228 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 8 ms 716 KB Output is correct
12 Correct 8 ms 720 KB Output is correct
13 Correct 12 ms 716 KB Output is correct
14 Correct 11 ms 696 KB Output is correct
15 Correct 577 ms 9756 KB Output is correct
16 Correct 520 ms 14684 KB Output is correct
17 Correct 543 ms 14440 KB Output is correct
18 Correct 507 ms 14128 KB Output is correct
19 Correct 492 ms 14228 KB Output is correct
20 Correct 377 ms 14284 KB Output is correct
21 Correct 368 ms 14300 KB Output is correct
22 Correct 360 ms 14276 KB Output is correct
23 Correct 481 ms 14108 KB Output is correct
24 Correct 517 ms 14240 KB Output is correct