Click here to Skip to main content
15,885,546 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
Contest Page | CodeChef[^]
I have used square root decomposition to solve the above question, but I don't understand why am I getting a TLE ? I think there is something additional about online judges or STL that I should have known...

What I have tried:

C++
#include <bits/stdc++.h>
using namespace std;
void preprocess(unordered_map<int, int> m[], int block_size, int n, vector<int> v[], vector<int> arr) {
	int block_index = -1;
	int x = 0;
	for (int i = 0; i < n; i++) {
		if(i % block_size == 0) block_index++;
		x ^= arr[i];
		v[block_index].push_back(x);
		m[block_index][x]++;
	}
}
int main() {
	int n, q; cin>>n>>q;
	int block_size = ceil(sqrt(n));
	unordered_map<int, int> m[block_size];
	vector<int> v[block_size], arr;
	int lazyxor[block_size] = {0};
	for (int i = 0; i < n; i++) {
		int temp; cin>>temp;
		arr.push_back(temp);
	}
	preprocess(m, block_size, n, v, arr);
	//--------------------------------------------divided into blocks
	while(q--) {
		int a, i, k;
		cin>>a>>i>>k;
		i--;
		int block_index = i/block_size;
		int offset = i%block_size;
		if(a == 1) {
			int xorval = arr[i]^k;
			if(offset != 0) {
				for (int o = 0; o < offset; o++) {
					m[block_index][v[block_index][o]]--;
					m[block_index][v[block_index][o]^lazyxor[block_index]]++;
					v[block_index][o] ^= lazyxor[block_index];
				}
				int xorval2 = xorval^lazyxor[block_index];
				while(offset < v[block_index].size()) {
					m[block_index][v[block_index][offset]]--;
					m[block_index][v[block_index][offset]^xorval2]++;
					v[block_index][offset] ^= xorval2;
					offset++;
				}
				lazyxor[block_index] = 0;
				block_index++;
			}
			while(block_index != block_size - 1) {
				lazyxor[block_index] ^= xorval;
				block_index++;
			}
			arr[i] = k;
		}
		else {
			int count = 0;
			for (int i = 0; i < block_index; i++) {
				count += m[i][lazyxor[i]^k];
			}
			for (int i = 0; i <= offset; i++) {
				if(v[block_index][i] == (lazyxor[block_index]^k)) count++;
			}
			cout<<count<<endl;
		}
	}
}
Posted
Updated 12-Dec-17 2:40am
Comments
Richard MacCutchan 12-Dec-17 4:42am    
Ask the people at CodeChef.

Quote:
but I don't understand why am I getting a TLE ? I think there is something additional about online judges or STL that I should have known...

The reason is simple: With CodeChef challenges, a strait forward answer is never the right answer, even if results are correct.
You can consider systematically that a very careful analyze of the problem will uncover a mathematical property or transform that lead to huge simplifications and speed up. Even a reasonably fast (general purpose) algorithm will be out performed by the mathematical property.

Said otherwise, it is a challenge because there is a clever handling.

I didn't studied this challenge, but usage of Xor smells like this kind of things.
 
Share this answer
 
v3
Because your code isn't finishing in the time allotted. Yeah, it may be quicker than the time required on YOUR MACHINE, but your machine isn't the judge.

The code has to run better than the time on the machine doing the judging, which may be slower that yours.

I can't give you the answer. That would be cheating. All I can tell you is your code is, how should I put this, "overly complex".
 
Share this answer
 
v2
Comments
Member 13571185 12-Dec-17 23:14pm    
The contest is over now....you can tell me where the complexity lies...
Dave Kreskowiak 12-Dec-17 23:28pm    
You can view the successful solutions yourself. Just go back top the page and click the "+" next to "Successful Submissions". There's a view button next to every one of them.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900