fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. // 14 important bits, giving max value of (2^15 - 1)
  6. #define BITS 14
  7.  
  8. #define MIN(a,b) (((a)<(b))?(a):(b))
  9. #define MAX(a,b) (((a)>(b))?(a):(b))
  10.  
  11. typedef struct {
  12. 	int count;
  13. 	int capacity;
  14. 	int *indexes; // position (i.e. j) where number is
  15. } INDEXLIST;
  16.  
  17. typedef struct NODE_STRUCT {
  18. 	struct NODE_STRUCT *left, *right;
  19. 	int minIndex, maxIndex;
  20. 	int value; // for a leaf
  21. 	INDEXLIST *indexList; // for a leaf
  22. } NODE;
  23.  
  24. INDEXLIST *add_index_to_list(INDEXLIST *list, int index) {
  25. 	if (!list) {
  26. 		list = (INDEXLIST *)malloc(sizeof(INDEXLIST));
  27. 		list->count = 0;
  28. 		list->capacity = 8;
  29. 		list->indexes = (int *)malloc(8 * sizeof(int));
  30. 	}
  31. 	if ((list->count + 1) >= list->capacity) {
  32. 		int newCapacity = list->capacity + 8;
  33. 		int *newList = (int *)malloc(newCapacity * sizeof(int));
  34. 		memcpy(newList, list->indexes, list->capacity * sizeof(int));
  35. 		free(list->indexes);
  36. 		list->indexes = newList;
  37. 		list->capacity = newCapacity;
  38. 	}
  39. 	list->indexes[list->count++] = index;
  40. 	return list;
  41. }
  42.  
  43. // expands range, adds to index list if at end, otherwise traverses based on bit
  44. NODE *add_index_to_node(NODE *node, int index, int value, int depth) {
  45. 	int bit;
  46.  
  47. 	// if node is null, we need to create a node
  48. 	if (!node) {
  49. 		node = (NODE *)malloc(sizeof(NODE));
  50. 		node->minIndex = 0x7fffffff;
  51. 		node->maxIndex = 0;
  52. 		node->indexList = NULL;
  53. 		node->left = node->right = NULL;
  54. 		node->value = 0;
  55. 	}
  56.  
  57. 	// expand node range
  58. 	node->minIndex = MIN(index, node->minIndex);
  59. 	node->maxIndex = MAX(index, node->maxIndex);
  60.  
  61. 	// get bit at this position
  62. 	bit = (BITS - depth);
  63.  
  64. 	// if bit is < 0, we are at a leaf and there are no more bits, just an index list
  65. 	if (bit < 0) {
  66. 		node->indexList = add_index_to_list(node->indexList, index);
  67. 		node->value = value;
  68. 		return node;
  69. 	}
  70.  
  71. 	// if he has THIS bit, go right, otherwise left
  72. 	if (value & (1 << bit)) {
  73. 		node->right = add_index_to_node(node->right, index, value, depth + 1);
  74. 	} else {
  75. 		node->left = add_index_to_node(node->left, index, value, depth + 1);
  76. 	}
  77.  
  78. 	return node;
  79. }
  80.  
  81. // will call with find_largest(root, value, p, q, 0)
  82. // NOTES:
  83. //		* it WILL return the maximum value from any node with index in range
  84. //		* once you have a non-zero value (found an index in range), it is no longer
  85. //				necessary to traverse the other side (left/right) than you started with
  86. int find_largest(NODE *node, int value, int minIndex, int maxIndex, int depth)
  87. {
  88. 	int i, result;
  89. 	INDEXLIST *list;
  90.  
  91. 	// make sure there's a node
  92. 	if (!node)
  93. 		return 0;
  94.  
  95. 	// make sure index ranges overlap
  96. 	if (minIndex > node->maxIndex || maxIndex < node->minIndex)
  97. 		return 0;
  98.  
  99. 	// if we're at maximum depth we have an INDEXLIST, check it and return
  100. 	list = node->indexList;
  101. 	if (list) {
  102. 		for (i = 0; i < list->count; i++) {
  103. 			if (list->indexes[i] >= minIndex && list->indexes[i] <= maxIndex) {
  104. 				return (value ^ node->value);
  105. 			}
  106. 		}
  107. 		return 0;
  108. 	}
  109.  
  110. 	// if bit of value is set, go left first (to get numbers that when xored with value would have 1 there)
  111. 	if (value & (1 << BITS - depth)) {
  112. 		result = find_largest(node->left, value, minIndex, maxIndex, depth + 1);
  113. 		if (!result)
  114. 			result = result = find_largest(node->right, value, minIndex, maxIndex, depth + 1);
  115. 	} else {
  116. 		result = find_largest(node->right, value, minIndex, maxIndex, depth + 1);
  117. 		if (!result)
  118. 			result = result = find_largest(node->left, value, minIndex, maxIndex, depth + 1);
  119. 	}
  120. 	return result;
  121. }
  122.  
  123. void free_node(NODE *node) {
  124. 	if (!node)
  125. 		return;
  126. 	if (node->indexList) {
  127. 		free(node->indexList->indexes);
  128. 		free(node->indexList);
  129. 	}
  130. 	free_node(node->left);
  131. 	free_node(node->right);
  132. 	free(node);
  133. }
  134.  
  135. int main() {
  136.  
  137. 	int T, N, Q, a, p, q, i, k, x, v, largest, index, result;
  138. 	NODE *root = NULL;
  139.  
  140. 	scanf("%d", &T);
  141.  
  142. 	while (T--) {
  143. 		scanf("%d %d", &N, &Q);
  144. 		for (i = 1; i <= N; i++) {
  145. 			scanf("%d", &x);
  146. 			root = add_index_to_node(root, i, x, 0);
  147. 		}
  148.  
  149. 		for (i = 0; i < Q; i++) {
  150. 			scanf("%d %d %d", &a, &p, &q);
  151. 			result = find_largest(root, a, p, q, 0);
  152. 			printf("%d\n", result);
  153. 		}
  154.  
  155. 		// free memory
  156. 		free_node(root);
  157. 		root = NULL;
  158. 	}
  159. }
Success #stdin #stdout 0s 2384KB
comments (?)
stdin
copy 
1  
15 8  
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  
10 6 10  
1023 7 7  
33 5 8  
182 5 10  
181 1 13  
5 10 15  
99 8 9  
33 10 14
stdout
copy 
13
1016
41
191
191
15
107
47
https://ideone.com/fNtrGb
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!