oj.uz

Submission #999962

# Submission time Handle Problem Language Result Execution time Memory
999962 2024-06-16T11:36:00 Z 0pt1mus23 XORanges (eJOI19_xoranges) C++14
100 / 100
 103 ms 22100 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 7 ms 12892 KB Output is correct
3 Correct 6 ms 12956 KB Output is correct
4 Correct 6 ms 12796 KB Output is correct
5 Correct 6 ms 12892 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 6 ms 12892 KB Output is correct
3 Correct 7 ms 12872 KB Output is correct
4 Correct 7 ms 12888 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 7 ms 12892 KB Output is correct
3 Correct 6 ms 12956 KB Output is correct
4 Correct 6 ms 12796 KB Output is correct
5 Correct 6 ms 12892 KB Output is correct
6 Correct 7 ms 12892 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 7 ms 12872 KB Output is correct
9 Correct 7 ms 12888 KB Output is correct
10 Correct 6 ms 12892 KB Output is correct
11 Correct 8 ms 13144 KB Output is correct
12 Correct 8 ms 13148 KB Output is correct
13 Correct 8 ms 13148 KB Output is correct
14 Correct 8 ms 13092 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 21892 KB Output is correct
2 Correct 87 ms 22100 KB Output is correct
3 Correct 103 ms 22052 KB Output is correct
4 Correct 75 ms 21560 KB Output is correct
5 Correct 85 ms 21728 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 7 ms 12892 KB Output is correct
3 Correct 6 ms 12956 KB Output is correct
4 Correct 6 ms 12796 KB Output is correct
5 Correct 6 ms 12892 KB Output is correct
6 Correct 7 ms 12892 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 7 ms 12872 KB Output is correct
9 Correct 7 ms 12888 KB Output is correct
10 Correct 6 ms 12892 KB Output is correct
11 Correct 8 ms 13144 KB Output is correct
12 Correct 8 ms 13148 KB Output is correct
13 Correct 8 ms 13148 KB Output is correct
14 Correct 8 ms 13092 KB Output is correct
15 Correct 95 ms 21892 KB Output is correct
16 Correct 87 ms 22100 KB Output is correct
17 Correct 103 ms 22052 KB Output is correct
18 Correct 75 ms 21560 KB Output is correct
19 Correct 85 ms 21728 KB Output is correct
20 Correct 87 ms 21868 KB Output is correct
21 Correct 91 ms 21760 KB Output is correct
22 Correct 87 ms 21816 KB Output is correct
23 Correct 79 ms 21556 KB Output is correct
24 Correct 79 ms 21556 KB Output is correct