Submission #763757

#	Time	Username	Problem	Language	Result	Execution time	Memory
763757		ivopav	XORanges (eJOI19_xoranges)	C++14	100 / 100	456 ms	10700 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

void mjenj(int ind,int val,vector<int>& lis){
    ind+=lis.size()/2;
    lis[ind]=val;
    while (ind>0){
        ind/=2;
        lis[ind]=lis[ind*2]^lis[ind*2+1];
    }
}

int que(int l,int r,vector<int>& lis,int ind,int l2,int r2){
    int lpom=l;
    int rpom=r;
    l+=lis.size()/2;
    r+=lis.size()/2;
    if (l<=l2 && r>=r2){
        return lis[ind];
    }
    
    if (r<l2 || l>r2){
        return 0;
    }
    return que(lpom,rpom,lis,ind*2,l2,(l2+r2)/2)^que(lpom,rpom,lis,ind*2+1,(r2+l2)/2+1,r2);
}

int main(){
    int n;
    int q;
    cin >> n >> q;
    vector<int> lisp={0};
    vector<int> lisnp={0};
    
    for (int i=0;i<pow(2,(int)(log2(n-1)+1))-1;i++){
        lisp.push_back(0);
        lisnp.push_back(0);
        
    }
    int kolp=0;
    int kolnp=0;
    for (int i=0;i<n;i++){ 
        int unos;
        cin >> unos;
        if (i%2==0){
            lisp.push_back(unos);
            kolnp++;
        }
        else {
            lisnp.push_back(unos);
            kolp++;
        }
    }
    for (int i=0;i<kolp;i++){
        lisp.push_back(0);
    }
    for (int i=0;i<kolnp;i++){
        lisnp.push_back(0);
    }
    
    for (int i=0;i<pow(2,(int)(log2(n-1)+1))-n;i++){
        lisp.push_back(0);
        lisnp.push_back(0);
        
    }
    for (int i=pow(2,(int)(log2(n-1)+1))-1;i>0;i--){
        lisp[i]=lisp[i*2]^lisp[i*2+1];
        lisnp[i]=lisnp[i*2]^lisnp[i*2+1];
        
    }
    for (int i=0;i<q;i++){
        //for (int j=0;j<lisp.size();j++){
        //    cout << lisp[j] << "\n";
        //}

        int vrs;
        int br1;
        int br2;
        cin >> vrs >> br1 >> br2;
        br1--;
        br2--;
        if (vrs==1){
            br2++;
            if (br1%2==0){
                br1/=2;
                mjenj(br1,br2,lisp);
            }
            else {
                br1/=2;
                mjenj(br1,br2,lisnp);
            }
        }
        else{
            if ((br2-br1+1)%2==0){
                cout << "0\n";
                continue;
            }
            if (br1%2==0){
                br1/=2;
                br2/=2; 
              //      cout << br1 << br2  << "\n";
                cout << que(br1,br2,lisp,1,1+lisp.size()/2-1,lisp.size()-1) << "\n";
            }
            else {
                br1/=2;
                br2/=2;
                cout << que(br1,br2,lisnp,1,1+lisnp.size()/2-1,lisnp.size()-1) << "\n";
            }
        }
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25