oj.uz

Submission #999724

# Submission time Handle Problem Language Result Execution time Memory
999724 2024-06-16T05:52:35 Z vjudge1 XORanges (eJOI19_xoranges) C++14
100 / 100
 109 ms 19768 KB 
/*       ==========================
        | Bismillahirrahmanirrahim | ⠀⠀ 
         ==========================
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠁⠸⢳⡄⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠃⠀⠀⢸⠸⠀⡠⣄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠃⠀⠀⢠⣞⣀⡿⠀⠀⣧⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⡖⠁⠀⠀⠀⢸⠈⢈⡇⠀⢀⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡴⠩⢠⡴⠀⠀⠀⠀⠀⠈⡶⠉⠀⠀⡸⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⠎⢠⣇⠏⠀⠀⠀⠀⠀⠀⠀⠁⠀⢀⠄⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢠⠏⠀⢸⣿⣴⠀⠀⠀⠀⠀⠀⣆⣀⢾⢟⠴⡇⠀⠀⠀⠀⠀<===== this is wolf, not everest
⠀⠀⠀⠀⠀⢀⣿⠀⠠⣄⠸⢹⣦⠀⠀⡄⠀⠀⢋⡟⠀⠀⠁⣇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡾⠁⢠⠀⣿⠃⠘⢹⣦⢠⣼⠀⠀⠉⠀⠀⠀⠀⢸⡀⠀⠀⠀⠀
⠀⠀⢀⣴⠫⠤⣶⣿⢀⡏⠀⠀⠘⢸⡟⠋⠀⠀⠀⠀⠀⠀⠀⠀⢳⠀⠀⠀⠀
⠐⠿⢿⣿⣤⣴⣿⣣⢾⡄⠀⠀⠀⠀⠳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠀
⠀⠀⠀⣨⣟⡍⠉⠚⠹⣇⡄⠀⠀⠀⠀⠀⠀⠀⠀⠈⢦⠀⠀⢀⡀⣾⡇⠀⠀
⠀⠀⢠⠟⣹⣧⠃⠀⠀⢿⢻⡀⢄⠀⠀⠀⠀⠐⣦⡀⣸⣆⠀⣾⣧⣯⢻⠀⠀
⠀⠀⠘⣰⣿⣿⡄⡆⠀⠀⠀⠳⣼⢦⡘⣄⠀⠀⡟⡷⠃⠘⢶⣿⡎⠻⣆⠀⠀
⠀⠀⠀⡟⡿⢿⡿⠀⠀⠀⠀⠀⠙⠀⠻⢯⢷⣼⠁⠁⠀⠀⠀⠙⢿⡄⡈⢆⠀
⠀⠀⠀⠀⡇⣿⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠦⠀⠀⠀⠀⠀⠀⡇⢹⢿⡀
⠀⠀⠀⠀⠁⠛⠓⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⠇⠁ 

m : 11059739 -> l ~23
p : 4567896467
*/
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define all(v) v.begin(), v.end()
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define str string
#define endl '\n'
#define drop(x) cout<<(x)<<endl;return;
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T> using ot = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 998244353, sze =8*1e5 + 10, inf = 1e9, prime = 4567896467;

struct genuisahmed{

    vector<int> lst;
    int n;
    int T1[sze];
    int T2[sze];
    genuisahmed(int _n,vector<int> arr){
        lst=arr;
        n=_n;
        build(1,0,n-1);
    }

    void build(int node,int l,int r){
        if(l==r){
            if((l+1)%2){
                T1[node]=lst[l];
            }
            else{
                T2[node]=lst[l];
            }
            return;
        }
        int mid = (l+r)/2;
        build(2*node,l,mid);
        build(2*node +1,mid+1,r);
        T1[node]= T1[node*2] ^ T1[node *2 +1];
        T2[node]= T2[node*2] ^ T2[node *2 +1];
    }

    int qry1(int node,int lx,int rx,int l,int r){
        if(l>rx || r<lx){
            return 0;
        }
        if(l>=lx && r<=rx){
            return T1[node];
        }
        int mid = (l+r)/2;
        int left = qry1(2*node,lx,rx,l,mid);
        int right = qry1(2*node +1,lx,rx,mid+1,r);
        return left ^ right;
    }
    int qry1(int l,int r){
        return qry1(1,l,r,0,n-1);
    }
    int qry2(int node,int lx,int rx,int l,int r){
        if(l>rx || r<lx){
            return 0;
        }
        if(l>=lx && r<=rx){
            return T2[node];
        }
        int mid = (l+r)/2;
        int left = qry2(2*node,lx,rx,l,mid);
        int right = qry2(2*node +1,lx,rx,mid+1,r);
        return left ^ right;
    }
    int qry2(int l,int r){
        return qry2(1,l,r,0,n-1);
    }

    void update(int node,int idx,int l,int r,int v){
        if(l==r){
            if((l+1)%2){
                T1[node]=v;
            }
            else{
                T2[node]=v;
            }
            return;
        }
        int mid = (l+r)/2;
        if(mid>=idx){
            update(2*node,idx,l,mid,v);
        }
        else{
            update(2*node+1,idx,mid+1,r,v);

        }
        T1[node]= T1[node*2] ^ T1[node *2 +1];
        T2[node]= T2[node*2] ^ T2[node *2 +1];
    }

    void update(int idx,int v){
        update(1,idx,0,n-1,v);
    }

    
};

void mal(){
    /*
        obvs :
        range len cut olanda cavab 0 olur

        cut segtree

        basladigi indexe gore, cut indexlilerin xoru goturulmur
    */
    // str s="abcdefgjk";
    // int n=s.size();
    // map<char,int> count;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j+i<=n;j++){
    //         str t="";
    //         for(int x=j;x<j+i;x++){
    //             t+=s[x];
    //             count[s[x]]++;
    //         }    
    //         cout<<t<<" ";
    //     }    
    //     cout<<endl;
    // }
    // for(auto v:s){
    //     cout<<v<<" "<<count[v]<<endl;
    // }

    int n,q;
    cin>>n>>q;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    genuisahmed ahmed(n,arr);
    vector<pii> tekqueries,cutqueries;
    while(q--){
        int op;
        cin>>op;

        if(op==2){
            int l,r;
            cin>>l>>r;

            if( (r-l+1)%2==0){
                cout<<0<<endl;
            }
            else{
                l--;
                r--;
                if((l+1)%2){
                    // tekden baslayir, cut indexliler sayilmiyacaq
                    cout<<ahmed.qry1(l,r)<<endl;
                }
                else{
                    // cutden basliyir, TEKLERI SIL
                    cout<<ahmed.qry2(l,r)<<endl;
                }
            }
        }
        else{
            int idx,v;
            cin>>idx>>v;
            ahmed.update(--idx,v);
        }
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;

    while (tt--) mal();
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct
3 Correct 6 ms 12892 KB Output is correct
4 Correct 6 ms 12888 KB Output is correct
5 Correct 7 ms 12940 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12892 KB Output is correct
2 Correct 7 ms 12892 KB Output is correct
3 Correct 6 ms 12784 KB Output is correct
4 Correct 6 ms 12892 KB Output is correct
5 Correct 6 ms 12892 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct
3 Correct 6 ms 12892 KB Output is correct
4 Correct 6 ms 12888 KB Output is correct
5 Correct 7 ms 12940 KB Output is correct
6 Correct 7 ms 12892 KB Output is correct
7 Correct 7 ms 12892 KB Output is correct
8 Correct 6 ms 12784 KB Output is correct
9 Correct 6 ms 12892 KB Output is correct
10 Correct 6 ms 12892 KB Output is correct
11 Correct 8 ms 13148 KB Output is correct
12 Correct 7 ms 13124 KB Output is correct
13 Correct 7 ms 13148 KB Output is correct
14 Correct 8 ms 12988 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 17500 KB Output is correct
2 Correct 88 ms 17496 KB Output is correct
3 Correct 109 ms 17500 KB Output is correct
4 Correct 74 ms 17496 KB Output is correct
5 Correct 77 ms 17496 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct
3 Correct 6 ms 12892 KB Output is correct
4 Correct 6 ms 12888 KB Output is correct
5 Correct 7 ms 12940 KB Output is correct
6 Correct 7 ms 12892 KB Output is correct
7 Correct 7 ms 12892 KB Output is correct
8 Correct 6 ms 12784 KB Output is correct
9 Correct 6 ms 12892 KB Output is correct
10 Correct 6 ms 12892 KB Output is correct
11 Correct 8 ms 13148 KB Output is correct
12 Correct 7 ms 13124 KB Output is correct
13 Correct 7 ms 13148 KB Output is correct
14 Correct 8 ms 12988 KB Output is correct
15 Correct 89 ms 17500 KB Output is correct
16 Correct 88 ms 17496 KB Output is correct
17 Correct 109 ms 17500 KB Output is correct
18 Correct 74 ms 17496 KB Output is correct
19 Correct 77 ms 17496 KB Output is correct
20 Correct 89 ms 19460 KB Output is correct
21 Correct 91 ms 19468 KB Output is correct
22 Correct 89 ms 19508 KB Output is correct
23 Correct 87 ms 19716 KB Output is correct
24 Correct 77 ms 19768 KB Output is correct