oj.uz

Submission #810800

# Submission time Handle Problem Language Result Execution time Memory
810800 2023-08-06T15:32:25 Z Acanikolic XORanges (eJOI19_xoranges) C++14
0 / 100
 174 ms 6488 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 << endl;
    			continue;
    		}
    		if(l == r) {
    			cout << a[l] << endl;
    			continue;
    		}
    		cout << (ft[(r-l+1) & 1].get(r) ^ ft[(r-l+1) & 1].get(l-1)) << '\n';
    	}
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -