Loading...
Submission
# When Author Problem Language CPU Memory
20826 2024-06-09 09:01:18 AHAMMED_99 Skyline C 0 ms 1532 kb Accepted
Test Cases
# CPU Memory Points
1 0 ms 1424 kb 1 Accepted
2 0 ms 1416 kb 1 Accepted
3 0 ms 1460 kb 1 Accepted
4 0 ms 1420 kb 1 Accepted
5 0 ms 1532 kb 1 Accepted
Source Code
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4. #include <stdbool.h>
  5.  
  6. // Structure to represent events
  7. typedef struct {
  8. int x;
  9. int height;
  10. int type; // 1 for start, -1 for end
  11. } Event;
  12.  
  13. // Comparator function for sorting events
  14. int compare(const void *a, const void *b) {
  15. Event *event1 = (Event *)a;
  16. Event *event2 = (Event *)b;
  17. if (event1->x != event2->x)
  18. return event1->x - event2->x;
  19. if (event1->type != event2->type)
  20. return event2->type - event1->type; // Start event before end event
  21. return event2->height - event1->height; // Higher height before lower height
  22. }
  23.  
  24. // Node of a max-heap
  25. typedef struct HeapNode {
  26. int value;
  27. int count;
  28. } HeapNode;
  29.  
  30. // Max-heap data structure
  31. typedef struct {
  32. HeapNode *nodes;
  33. int size;
  34. int capacity;
  35. } MaxHeap;
  36.  
  37. // Function to create a max-heap
  38. MaxHeap* createMaxHeap(int capacity) {
  39. MaxHeap *heap = (MaxHeap *)malloc(sizeof(MaxHeap));
  40. heap->nodes = (HeapNode *)malloc(sizeof(HeapNode) * capacity);
  41. heap->size = 0;
  42. heap->capacity = capacity;
  43. return heap;
  44. }
  45.  
  46. // Swap function
  47. void swap(HeapNode *a, HeapNode *b) {
  48. HeapNode temp = *a;
  49. *a = *b;
  50. *b = temp;
  51. }
  52.  
  53. // Heapify function
  54. void heapify(MaxHeap *heap, int i) {
  55. int largest = i;
  56. int left = 2 * i + 1;
  57. int right = 2 * i + 2;
  58.  
  59. if (left < heap->size && heap->nodes[left].value > heap->nodes[largest].value)
  60. largest = left;
  61. if (right < heap->size && heap->nodes[right].value > heap->nodes[largest].value)
  62. largest = right;
  63.  
  64. if (largest != i) {
  65. swap(&heap->nodes[i], &heap->nodes[largest]);
  66. heapify(heap, largest);
  67. }
  68. }
  69.  
  70. // Function to insert a value into the max-heap
  71. void insertHeap(MaxHeap *heap, int value) {
  72. bool found = false;
  73. for (int i = 0; i < heap->size; i++) {
  74. if (heap->nodes[i].value == value) {
  75. heap->nodes[i].count++;
  76. found = true;
  77. break;
  78. }
  79. }
  80. if (!found) {
  81. heap->nodes[heap->size].value = value;
  82. heap->nodes[heap->size].count = 1;
  83. heap->size++;
  84. }
  85. for (int i = heap->size / 2 - 1; i >= 0; i--)
  86. heapify(heap, i);
  87. }
  88.  
  89. // Function to delete a value from the max-heap
  90. void deleteHeap(MaxHeap *heap, int value) {
  91. for (int i = 0; i < heap->size; i++) {
  92. if (heap->nodes[i].value == value) {
  93. heap->nodes[i].count--;
  94. if (heap->nodes[i].count == 0) {
  95. swap(&heap->nodes[i], &heap->nodes[heap->size - 1]);
  96. heap->size--;
  97. for (int j = heap->size / 2 - 1; j >= 0; j--)
  98. heapify(heap, j);
  99. }
  100. break;
  101. }
  102. }
  103. }
  104.  
  105. // Function to get the maximum value from the max-heap
  106. int getMaxHeap(MaxHeap *heap) {
  107. return heap->size > 0 ? heap->nodes[0].value : 0;
  108. }
  109.  
  110. int main() {
  111. int N;
  112. scanf("%d", &N);
  113. Event events[2 * N];
  114. int eventCount = 0;
  115.  
  116. // Reading input and creating events
  117. for (int i = 0; i < N; i++) {
  118. int L, R, H;
  119. scanf("%d %d %d", &L, &R, &H);
  120. events[eventCount++] = (Event){L, H, 1}; // start of the building
  121. events[eventCount++] = (Event){R, H, -1}; // end of the building
  122. }
  123.  
  124. // Sorting events
  125. qsort(events, eventCount, sizeof(Event), compare);
  126.  
  127. MaxHeap *heap = createMaxHeap(2 * N);
  128. int prevHeight = 0;
  129.  
  130. for (int i = 0; i < eventCount; i++) {
  131. if (events[i].type == 1) { // start of a building
  132. insertHeap(heap, events[i].height);
  133. } else { // end of a building
  134. deleteHeap(heap, events[i].height);
  135. }
  136.  
  137. int currentMaxHeight = getMaxHeap(heap);
  138. if (currentMaxHeight != prevHeight) {
  139. printf("%d %d\n", events[i].x, currentMaxHeight);
  140. prevHeight = currentMaxHeight;
  141. }
  142. }
  143.  
  144. free(heap->nodes);
  145. free(heap);
  146. return 0;
  147. }
  148.