oj.uz

Submission #334038

# Submission time Handle Problem Language Result Execution time Memory
334038 2020-12-08T07:21:53 Z limabeans XORanges (eJOI19_xoranges) C++17
100 / 100
 194 ms 13596 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


template<typename T> struct segtree {
    
    T merge(T x, T y) {
	return x^y;
    }
    int n;
    vector<T> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.assign(n*4, 0);
    }

    void upd(int v, int tl, int tr, int i, T dx) {
	if (tl == tr) {
	    t[v] = dx;
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,dx);
	    } else {
		upd(2*v+1,tm+1,tr,i,dx);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    T qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return 0;
	}
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
    }
};


int n,q;
int a[maxn];
segtree<int> t[2];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q;
    t[0].init(n+10);
    t[1].init(n+10);
    
    for (int i=1; i<=n; i++) {
	cin>>a[i];
	t[i%2].upd(1,1,n,i,a[i]);
    }


    while (q--) {
	int op;
	cin>>op;
	if (op==1) {
	    int i,x;
	    cin>>i>>x;
	    a[i] = x;
	    t[i%2].upd(1,1,n,i,x);
	} else {
	    int l,r;
	    cin>>l>>r;
	    if (l%2!=r%2) {
		cout<<"0\n";
		continue;
	    }
	    int res = t[l%2].qry(1,1,n,l,r);
	    cout<<res<<"\n";	    
	}
    }
    
    
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 4 ms 620 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 12524 KB Output is correct
2 Correct 194 ms 13596 KB Output is correct
3 Correct 186 ms 13460 KB Output is correct
4 Correct 155 ms 13116 KB Output is correct
5 Correct 155 ms 13164 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 4 ms 620 KB Output is correct
15 Correct 188 ms 12524 KB Output is correct
16 Correct 194 ms 13596 KB Output is correct
17 Correct 186 ms 13460 KB Output is correct
18 Correct 155 ms 13116 KB Output is correct
19 Correct 155 ms 13164 KB Output is correct
20 Correct 187 ms 13164 KB Output is correct
21 Correct 186 ms 13292 KB Output is correct
22 Correct 182 ms 13292 KB Output is correct
23 Correct 155 ms 13164 KB Output is correct
24 Correct 158 ms 13164 KB Output is correct