oj.uz

Submission #592256

# Submission time Handle Problem Language Result Execution time Memory
592256 2022-07-08T19:59:21 Z Iwanttobreakfree XORanges (eJOI19_xoranges) C++
100 / 100
 504 ms 10344 KB 
#include <iostream>
#include <vector>
using namespace std;
void build(int n,int l,int r,vector<int>& t,vector<int>& li){
    //cout<<l<<' '<<r<<'\n';
    if(l>r)return;
    if(l==r)t[n]=li[l];
    else{
        int mid=(r+l)/2;
        build(n<<1,l,mid,t,li);
        build((n<<1)+1,mid+1,r,t,li);
        t[n]=t[n<<1]^t[(n<<1)+1];
    }
}
void p_upd(int n,int l,int r,vector<int>& t,int x,int y){
    if(l>x||r<x)return;
    if(l==r&&l==x)t[n]=y;
    else{
        int mid=(r+l)/2;
        p_upd(n<<1,l,mid,t,x,y);
        p_upd((n<<1)+1,mid+1,r,t,x,y);
        t[n]=t[n<<1]^t[(n<<1)+1];
    }
}
int val(int n,int l,int r,vector<int>& t,int x,int y){
    if(l>y||r<x)return 0;
    if(l>=x&&r<=y)return t[n];
    else{
        int mid=(r+l)/2;
        int valls=val(n<<1,l,mid,t,x,y);
        int valrs=val((n<<1)+1,mid+1,r,t,x,y);
        return valls^valrs;
    }
}
int main(){
    int n,q,t,x,y;
    cin>>n>>q;
    vector<int> l1(n/2),l2(n-n/2);
    vector<int> t1(2*n),t2(4*(n-n/2));
    for(int i=0;i<n;i++){
        cin>>x;
        if(i&1)l1[i/2]=x;
        else l2[i/2]=x;
    }
    //for(int i=0;i<l2.size();i++)cout<<l2[i]<<' ';
    if(n>1)build(1,0,n/2-1,t1,l1);
    build(1,0,n-n/2-1,t2,l2);
    //cout<<"ok ";
    while(q--){
        cin>>t>>x>>y;
        if(t==1){
            if(x&1)p_upd(1,0,n-n/2-1,t2,(x-1)/2,y);
            else p_upd(1,0,n/2-1,t1,(x-1)/2,y);
        }else{
            if((y-x)&1)cout<<0<<'\n';
            else{
                if(x&1)cout<<val(1,0,n-n/2-1,t2,(x-1)/2,(y-1)/2);
                else cout<<val(1,0,n/2-1,t1,(x-1)/2,(y-1)/2);
                cout<<'\n';
            }
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 308 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 308 KB Output is correct
11 Correct 9 ms 468 KB Output is correct
12 Correct 11 ms 508 KB Output is correct
13 Correct 12 ms 468 KB Output is correct
14 Correct 12 ms 496 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 6184 KB Output is correct
2 Correct 493 ms 10344 KB Output is correct
3 Correct 489 ms 10240 KB Output is correct
4 Correct 472 ms 9824 KB Output is correct
5 Correct 483 ms 9984 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 308 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 308 KB Output is correct
11 Correct 9 ms 468 KB Output is correct
12 Correct 11 ms 508 KB Output is correct
13 Correct 12 ms 468 KB Output is correct
14 Correct 12 ms 496 KB Output is correct
15 Correct 504 ms 6184 KB Output is correct
16 Correct 493 ms 10344 KB Output is correct
17 Correct 489 ms 10240 KB Output is correct
18 Correct 472 ms 9824 KB Output is correct
19 Correct 483 ms 9984 KB Output is correct
20 Correct 452 ms 9932 KB Output is correct
21 Correct 393 ms 9980 KB Output is correct
22 Correct 395 ms 9916 KB Output is correct
23 Correct 459 ms 9896 KB Output is correct
24 Correct 475 ms 9844 KB Output is correct