Submission #404123

#	Time	Username	Problem	Language	Result	Execution time	Memory
404123		Pichon5	XORanges (eJOI19_xoranges)	C++17	100 / 100	729 ms	11324 KiB

xoranges

#include<bits/stdc++.h>
#include <chrono>
#include <thread>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const int tam=2*1e5;
int T1[4*tam];
int T2[4*tam];
vi v;
void init(int nodo, int b, int e){
    int mid=(b+e)/2,L=2*nodo+1,R=L+1;
    if(b==e){
        if(b%2){
            T2[nodo]=v[b];
        }else{
            T1[nodo]=v[b];
        }
        return;
    }
    init(L,b,mid);
    init(R,mid+1,e);
    T1[nodo]=(T1[L]^T1[R]);
    T2[nodo]=(T2[L]^T2[R]);
}
int query1(int nodo, int b, int e, int izq, int der){
    int mid=(b+e)/2,L=2*nodo+1,R=L+1;
    if(b>=izq && e<=der){
        return T1[nodo];
    }
    if(der<=mid)return query1(L,b,mid,izq,der);
    if(izq>=mid+1)return query1(R,mid+1,e,izq,der);
    int A=query1(L,b,mid,izq,der);
    int B=query1(R,mid+1,e,izq,der);
    return (A^B);
}
int query2(int nodo, int b, int e, int izq, int der){
    int mid=(b+e)/2,L=2*nodo+1,R=L+1;
    if(b>=izq && e<=der){
        return T2[nodo];
    }
    if(der<=mid)return query2(L,b,mid,izq,der);
    if(izq>=mid+1)return query2(R,mid+1,e,izq,der);
    int A=query2(L,b,mid,izq,der);
    int B=query2(R,mid+1,e,izq,der);
    return (A^B);
}
void update(int nodo, int b, int e, int pos, int val){
    int mid=(b+e)/2,L=2*nodo+1,R=L+1;
    if(b==e){
        if(pos%2==0){
            T1[nodo]=val;
        }else{
            T2[nodo]=val;
        }
        return;
    }
    if(pos<=mid){
        update(L,b,mid,pos,val);
    }else{
        update(R,mid+1,e,pos,val);
    }
    T1[nodo]=(T1[L]^T1[R]);
    T2[nodo]=(T2[L]^T2[R]);
}
int main()
{
    int n,q,x;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>x;
        v.pb(x);
    }
    init(0,0,n-1);
    int c,a,b;
    while(q--){
        cin>>c>>a>>b;
        if(c==2){
            a--;b--;
            //query
            if((b-a+1)%2==0){
                cout<<0<<endl;
            }else{
                if(a%2==0){
                    cout<<query1(0,0,n-1,a,b)<<endl;
                }else{
                    cout<<query2(0,0,n-1,a,b)<<endl;
                }
            }
        }else{
            a--;
            update(0,0,n-1,a,b);
        }
    }

    return 0;
}

Compilation message (stderr)

xoranges.cpp:15: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   15 | #pragma GCC optimization ("O3")
      | 
xoranges.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("unroll-loops")
      |

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