oj.uz

Submission #268077

# Submission time Handle Problem Language Result Execution time Memory
268077 2020-08-16T08:20:21 Z VusetOrucov XORanges (eJOI19_xoranges) C++17
100 / 100
 641 ms 16248 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define black_tree tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define gp __gnu_pbds
#define INF 1000000000
#define MOD 1000000007
#define MAX 200001
#define endl '\n'
#define ll long long
#define ld long double
#define lli long long int
#define ull unsigned long long
#define ulli unsigned long long int
#define pb push_back
#define pf push_front
#define ook order_of_key
#define fbo find_by_order
#define np next_permutation
#define mp make_pair
#define eb emplace_back 
#define me max_element
#define lb lower_bound 
#define ub upper_bound
#define bs binary_search
#define ff first
#define ss second
using namespace std;
using namespace gp;
ll n,q,k,u,v,a[MAX],dp0[4*MAX],dp1[4*MAX];
void buildTree(ll v,ll l,ll r){
    if(l==r){
    	if(l%2==1){
    		dp0[v]=a[l];
		}
		else{
			dp1[v]=a[l];
		}
        return;
    }
    ll m=(l+r)/2;
    buildTree(2*v,l,m);
    buildTree(2*v+1,m+1,r);
    dp0[v]=dp0[2*v]^dp0[2*v+1];
    dp1[v]=dp1[2*v]^dp1[2*v+1];
}
ll get(ll v,ll l,ll r,ll i1,ll i2,ll t){
    if(r<i1 || l>i2){
    	return 0;
	}
    else if(l>=i1 && r<=i2){
    	if(t==1){
    		return dp0[v];
		}
		else{
			return dp1[v];
		}
	}
    ll m=(l+r)/2;
    ll ans=get(2*v,l,m,i1,min(m,i2),t);
    ll sum=get(2*v+1,m+1,r,max(m+1,i1),i2,t);
    return ans^sum;
}
void updateTree(ll v,ll l,ll r,ll i,ll value){
    if(l==r){
    	if(i%2==1){
    		dp0[v]=value;
		}
        else{
        	dp1[v]=value;
		}
        return;
    }
    ll m=(l+r)/2;
    if(i<=m){
    	updateTree(2*v,l,m,i,value);
	}
    else{
    	updateTree(2*v+1,m+1,r,i,value);
	}
    dp0[v]=dp0[2*v]^dp0[2*v+1];
    dp1[v]=dp1[2*v]^dp1[2*v+1];
}
int main(){
	ios::sync_with_stdio(true);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	buildTree(1,1,n);
	while(q--){
		cin>>k>>u>>v;
		if(k==1){
			updateTree(1,1,n,u,v);
		}
		else{
			if(u%2!=v%2){
				cout<<"0\n";
			}
			else{
				cout<<get(1,1,n,u,v,u%2)<<endl;
			}
		}
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 12 ms 768 KB Output is correct
12 Correct 14 ms 800 KB Output is correct
13 Correct 12 ms 896 KB Output is correct
14 Correct 15 ms 896 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 16248 KB Output is correct
2 Correct 571 ms 16120 KB Output is correct
3 Correct 560 ms 16120 KB Output is correct
4 Correct 496 ms 15864 KB Output is correct
5 Correct 480 ms 15828 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 12 ms 768 KB Output is correct
12 Correct 14 ms 800 KB Output is correct
13 Correct 12 ms 896 KB Output is correct
14 Correct 15 ms 896 KB Output is correct
15 Correct 535 ms 16248 KB Output is correct
16 Correct 571 ms 16120 KB Output is correct
17 Correct 560 ms 16120 KB Output is correct
18 Correct 496 ms 15864 KB Output is correct
19 Correct 480 ms 15828 KB Output is correct
20 Correct 641 ms 16120 KB Output is correct
21 Correct 561 ms 15992 KB Output is correct
22 Correct 583 ms 15864 KB Output is correct
23 Correct 504 ms 15736 KB Output is correct
24 Correct 507 ms 15736 KB Output is correct