oj.uz

Submission #404123

# Submission time Handle Problem Language Result Execution time Memory
404123 2021-05-13T19:55:52 Z Pichon5 XORanges (eJOI19_xoranges) C++17
100 / 100
 729 ms 11324 KB 
#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

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.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 316 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 308 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 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 316 KB Output is correct
7 Correct 2 ms 312 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 308 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 12 ms 624 KB Output is correct
12 Correct 12 ms 628 KB Output is correct
13 Correct 16 ms 596 KB Output is correct
14 Correct 20 ms 624 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 11324 KB Output is correct
2 Correct 668 ms 11296 KB Output is correct
3 Correct 676 ms 11280 KB Output is correct
4 Correct 681 ms 11120 KB Output is correct
5 Correct 661 ms 10924 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 316 KB Output is correct
7 Correct 2 ms 312 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 308 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 12 ms 624 KB Output is correct
12 Correct 12 ms 628 KB Output is correct
13 Correct 16 ms 596 KB Output is correct
14 Correct 20 ms 624 KB Output is correct
15 Correct 729 ms 11324 KB Output is correct
16 Correct 668 ms 11296 KB Output is correct
17 Correct 676 ms 11280 KB Output is correct
18 Correct 681 ms 11120 KB Output is correct
19 Correct 661 ms 10924 KB Output is correct
20 Correct 511 ms 11188 KB Output is correct
21 Correct 514 ms 11052 KB Output is correct
22 Correct 511 ms 11072 KB Output is correct
23 Correct 625 ms 11096 KB Output is correct
24 Correct 639 ms 10988 KB Output is correct