oj.uz

Submission #810829

# Submission time Handle Problem Language Result Execution time Memory
810829 2023-08-06T16:05:22 Z Acanikolic XORanges (eJOI19_xoranges) C++14
100 / 100
 82 ms 10996 KB 
#include <bits/stdc++.h>
			 		
#define int long long 
			 
#define pb push_back 
			
#define F first
			 
#define S second
			 
using namespace std;
			 
const int N = 2e5+10;
			 
const int mod = 1e9+7;
			 
const int inf = 1e18;
 
int a[N];
 
struct fenwick {
	vector<int>fenw;
	void build(int n) {
		fenw.resize(n+1);
	}
	void update(int index,int n,int val) {
		while(index <= n) {
			fenw[index] ^= val;
			index += index & -index;
		}
	}
	int get(int x) {
		int ret = 0;
		while(x >= 1) {
			ret ^= fenw[x];
			x -= x & -x;
		}
		return ret;
	}
};
		
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
	 
    int n,Q;
    cin >> n >> Q;
    fenwick ft[2];
    ft[0].build(n);
    ft[1].build(n);
    for(int i=1;i<=n;i++) {
    	cin >> a[i];
    	ft[i & 1].update(i,n,a[i]);
    }
    //cout << ft[1].get(n) << ' ' << ft[0].get(n) << endl;
    while(Q--) {
    	int type;
    	cin >> type;
    	if(type & 1) {
    		int index,val;
    		cin >> index >> val;
    		ft[index & 1].update(index,n,a[index]);
    		a[index] = val;
    		ft[index & 1].update(index,n,a[index]);
    	}
    	else {
    		int l,r;
    		cin >> l >> r;
    		if((r-l+1) % 2 == 0) {
    			cout << 0 << '\n';
    			continue;
    		}
    		cout << (ft[l & 1].get(r) ^ ft[l & 1].get(l-1)) << '\n';
    	}
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 240 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 476 KB Output is correct
14 Correct 2 ms 468 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6120 KB Output is correct
2 Correct 72 ms 10956 KB Output is correct
3 Correct 70 ms 10996 KB Output is correct
4 Correct 67 ms 10704 KB Output is correct
5 Correct 66 ms 10700 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 240 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 476 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 67 ms 6120 KB Output is correct
16 Correct 72 ms 10956 KB Output is correct
17 Correct 70 ms 10996 KB Output is correct
18 Correct 67 ms 10704 KB Output is correct
19 Correct 66 ms 10700 KB Output is correct
20 Correct 73 ms 10776 KB Output is correct
21 Correct 66 ms 10764 KB Output is correct
22 Correct 82 ms 10700 KB Output is correct
23 Correct 67 ms 10720 KB Output is correct
24 Correct 66 ms 10636 KB Output is correct