Loading...
Submission
# When Author Problem Language CPU Memory
20825 2024-06-09 08:58:11 AHAMMED_99 Skyline C 0 ms 1552 kb Wrong Answer - 1
Test Cases
# CPU Memory Points
1 0 ms 1552 kb 0 Wrong Answer
2 0 ms 0 kb 0 Skipped
3 0 ms 0 kb 0 Skipped
4 0 ms 0 kb 0 Skipped
5 0 ms 0 kb 0 Skipped
Source Code
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4.  
  5. // Structure to represent events
  6. typedef struct {
  7. int x;
  8. int height;
  9. int type; // 1 for start, -1 for end
  10. } Event;
  11.  
  12. // Comparator function for sorting events
  13. int compare(const void* a, const void* b) {
  14. Event* event1 = (Event*)a;
  15. Event* event2 = (Event*)b;
  16. if (event1->x != event2->x)
  17. return event1->x - event2->x;
  18. // If two events have the same x-coordinate, prioritize the start of a building over the end of a building
  19. return (event1->type * event1->height) - (event2->type * event2->height);
  20. }
  21.  
  22. // A utility function to swap two elements
  23. void swap(int* a, int* b) {
  24. int t = *a;
  25. *a = *b;
  26. *b = t;
  27. }
  28.  
  29. // Max-heap implementation
  30. void heapify(int arr[], int n, int i) {
  31. int largest = i; // Initialize largest as root
  32. int l = 2 * i + 1; // left = 2*i + 1
  33. int r = 2 * i + 2; // right = 2*i + 2
  34. if (l < n && arr[l] > arr[largest])
  35. largest = l;
  36. if (r < n && arr[r] > arr[largest])
  37. largest = r;
  38. if (largest != i) {
  39. swap(&arr[i], &arr[largest]);
  40. heapify(arr, n, largest);
  41. }
  42. }
  43.  
  44. void insertHeap(int heap[], int* size, int value) {
  45. heap[*size] = value;
  46. (*size)++;
  47. for (int i = (*size) / 2 - 1; i >= 0; i--)
  48. heapify(heap, *size, i);
  49. }
  50.  
  51. void deleteHeap(int heap[], int* size, int value) {
  52. int i;
  53. for (i = 0; i < *size; i++) {
  54. if (heap[i] == value)
  55. break;
  56. }
  57. swap(&heap[i], &heap[*size - 1]);
  58. (*size)--;
  59. for (int i = (*size) / 2 - 1; i >= 0; i--)
  60. heapify(heap, *size, i);
  61. }
  62.  
  63. int getMaxHeap(int heap[], int size) {
  64. return size > 0 ? heap[0] : 0;
  65. }
  66.  
  67. int main() {
  68. int N;
  69. scanf("%d", &N);
  70. Event events[2 * N];
  71. int eventCount = 0;
  72.  
  73. // Reading input and creating events
  74. for (int i = 0; i < N; i++) {
  75. int L, R, H;
  76. scanf("%d %d %d", &L, &R, &H);
  77. events[eventCount++] = (Event){L, H, 1}; // start of the building
  78. events[eventCount++] = (Event){R, H, -1}; // end of the building
  79. }
  80.  
  81. // Sorting events
  82. qsort(events, eventCount, sizeof(Event), compare);
  83.  
  84. int maxHeap[2 * N];
  85. int heapSize = 0;
  86. int prevHeight = 0;
  87.  
  88. for (int i = 0; i < eventCount; i++) {
  89. if (events[i].type == 1) { // start of a building
  90. insertHeap(maxHeap, &heapSize, events[i].height);
  91. } else { // end of a building
  92. deleteHeap(maxHeap, &heapSize, events[i].height);
  93. }
  94.  
  95. int currentMaxHeight = getMaxHeap(maxHeap, heapSize);
  96. if (currentMaxHeight != prevHeight) {
  97. printf("%d %d\n", events[i].x, currentMaxHeight);
  98. prevHeight = currentMaxHeight;
  99. }
  100. }
  101.  
  102. return 0;
  103. }
  104.