oj.uz

Submission #236349

# Submission time Handle Problem Language Result Execution time Memory
236349 2020-06-01T13:03:50 Z Dremix10 XORanges (eJOI19_xoranges) C++17
100 / 100
 809 ms 11484 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
//#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define mod (int)1e9+7
#define N (int)1e5*2+1

struct ano{

int even;
int odd;

};

int arr[N];
ano seg[4*N];

ano join(ano a, ano b, bool even){
    ano res;
    if(even){
        res.even=a.even^b.even;
        res.odd=a.odd^b.odd;
    }
    else{
        res.even=a.even^b.odd;
        res.odd=a.odd^b.even;
    }
    return res;
}

void build(int s, int e, int idx){
    if(s==e){
        seg[idx].odd=arr[s];
      //  cout<<"leaf "<<s<<" "<<e<<" "<<seg[idx].odd<<endl;
        return;
    }
    int mid=(s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);

    bool even=true;
    if((mid-s+1)%2)
        even=false;
    seg[idx]=join(seg[idx*2],seg[idx*2+1],even);
  //  cout<<"up "<<s<<" "<<e<<" "<<seg[idx].odd<<" "<<seg[idx].even<<endl;
}

void update(int s,int e, int idx, int k, int u){
    if(s==e && s==k){
        seg[idx].odd=u;
        return;
    }
    if(s>k || e<k)
        return;
    int mid=(s+e)/2;
    update(s,mid,idx*2,k,u);
    update(mid+1,e,idx*2+1,k,u);

    bool even=true;
    if((mid-s+1)%2)
        even=false;
    seg[idx]=join(seg[idx*2],seg[idx*2+1],even);
}

ano query(int s, int e, int idx, int qs, int qe){
    if(qs<=s && e<=qe){
     //   cout<<"init "<<s<<" "<<e<<" "<<seg[idx].odd<<" "<<seg[idx].even<<endl;
        return seg[idx];
    }
    if(s>qe || e<qs)
        return {0,-1};

    int mid=(s+e)/2;
    ano p1,p2;
    p1=query(s,mid,idx*2,qs,qe);
    p2=query(mid+1,e,idx*2+1,qs,qe);

  //  cout<<s<<" "<<e<<endl;
 //   cout<<p1.odd<<" "<<p1.even<<" "<<p2.odd<<" "<<p2.even<<endl;

    if(p1.odd==-1)
        return p2;
    if(p2.odd==-1)
        return p1;

    bool even=true;
    if((min(mid,qe)-max(s,qs)+1)%2)
        even=false;
    return join(p1,p2,even);
}

int main (){
//fastio;

int n,q;
cin>>n>>q;

int i;
for(i=1;i<=n;i++)
    cin>>arr[i];

build(1,n,1);
while(q--){
    int task,x,y;
    cin>>task>>x>>y;
    if(task==1)
        update(1,n,1,x,y);
    else if((x-y+1)%2)
        cout<<query(1,n,1,x,y).odd<<endl;
    else
        cout<<0<<endl;

}


}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 26 ms 768 KB Output is correct
12 Correct 20 ms 640 KB Output is correct
13 Correct 23 ms 640 KB Output is correct
14 Correct 22 ms 640 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 11484 KB Output is correct
2 Correct 809 ms 11352 KB Output is correct
3 Correct 790 ms 11460 KB Output is correct
4 Correct 773 ms 11128 KB Output is correct
5 Correct 761 ms 11000 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 26 ms 768 KB Output is correct
12 Correct 20 ms 640 KB Output is correct
13 Correct 23 ms 640 KB Output is correct
14 Correct 22 ms 640 KB Output is correct
15 Correct 795 ms 11484 KB Output is correct
16 Correct 809 ms 11352 KB Output is correct
17 Correct 790 ms 11460 KB Output is correct
18 Correct 773 ms 11128 KB Output is correct
19 Correct 761 ms 11000 KB Output is correct
20 Correct 621 ms 11156 KB Output is correct
21 Correct 629 ms 11000 KB Output is correct
22 Correct 622 ms 11084 KB Output is correct
23 Correct 749 ms 11000 KB Output is correct
24 Correct 749 ms 11012 KB Output is correct