Submission #41689

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
41689	2018-02-20T17:11:07 Z	MatheusLealV	XOR (IZhO12_xor)	C++14	100 / 100	292 ms	65788 KB

xor

#include <bits/stdc++.h>
#define N 250005
#define logn 31
using namespace std;

int n, k, v[N], dp[N], ans;

struct node
{
	node *prox[2];

	int best;

	node() {prox[0] = prox[1] = NULL, best = 0;}
};

node *root;

inline void add(int num, int id, node *root)
{
   root->best = id;

   for(int i = logn; i >= 0; i--)
   {
      int bit = (num & (1<<i)) ? 1:0;

      if(!root->prox[bit]) root->prox[bit] = new node();

      root = root->prox[bit];

      root->best = id;
   }
}

inline int query(node *root, int x)
{
	for(int i = logn; i >= 0; i--)
	{
		int bit = (x & (1<<i)) ? 1:0;

		int aux = (k & (1<<i)) ? 1:0;

		if(aux)
		{
			if(!root->prox[!bit]) return -1;

			root = root->prox[!bit];
		}
		else
		{
			if(root->prox[!bit]) return root->prox[!bit]->best;

			root = root->prox[bit];
		}
	}

	return root->best;
}

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

	cin>>n>>k;

	root = new node();

	for(int i = 1; i <= n; i++)
	{
		cin>>v[i];

		v[i] ^= v[i - 1];

		add(v[i], i, root);
	}

	for(int i = 1; i <= n; i++)
	{
		dp[i] = query(root, v[i - 1]);

		ans = max(ans, dp[i] - i + 1);
	}

	for(int i = 1; i <= n; i++) if(dp[i] - i + 1 == ans)
	{
		cout<<i<<" "<<ans<<"\n";

		return 0;
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	368 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	592 KB	Output is correct
4	Correct	2 ms	740 KB	Output is correct
5	Correct	12 ms	2160 KB	Output is correct
6	Correct	14 ms	2688 KB	Output is correct
7	Correct	14 ms	2956 KB	Output is correct
8	Correct	20 ms	3208 KB	Output is correct
9	Correct	108 ms	29140 KB	Output is correct
10	Correct	98 ms	29244 KB	Output is correct
11	Correct	103 ms	29244 KB	Output is correct
12	Correct	100 ms	29244 KB	Output is correct
13	Correct	103 ms	29244 KB	Output is correct
14	Correct	104 ms	29256 KB	Output is correct
15	Correct	91 ms	29256 KB	Output is correct
16	Correct	127 ms	29256 KB	Output is correct
17	Correct	290 ms	59980 KB	Output is correct
18	Correct	265 ms	61940 KB	Output is correct
19	Correct	290 ms	63992 KB	Output is correct
20	Correct	292 ms	65788 KB	Output is correct