Submission
# | When | Author | Problem | Language | CPU | Memory | |
---|---|---|---|---|---|---|---|
20826 | 2024-06-09 09:01:18 | AHAMMED_99 | Skyline | C | 0 ms | 1532 kb | Accepted |
Source Code
#include <stdio.h> #include <stdlib.h> #include <limits.h> #include <stdbool.h> // Structure to represent events typedef struct { int x; int height; int type; // 1 for start, -1 for end } Event; // Comparator function for sorting events int compare(const void *a, const void *b) { Event *event1 = (Event *)a; Event *event2 = (Event *)b; if (event1->x != event2->x) return event1->x - event2->x; if (event1->type != event2->type) return event2->type - event1->type; // Start event before end event return event2->height - event1->height; // Higher height before lower height } // Node of a max-heap typedef struct HeapNode { int value; int count; } HeapNode; // Max-heap data structure typedef struct { HeapNode *nodes; int size; int capacity; } MaxHeap; // Function to create a max-heap MaxHeap* createMaxHeap(int capacity) { heap->size = 0; heap->capacity = capacity; return heap; } // Swap function void swap(HeapNode *a, HeapNode *b) { HeapNode temp = *a; *a = *b; *b = temp; } // Heapify function void heapify(MaxHeap *heap, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < heap->size && heap->nodes[left].value > heap->nodes[largest].value) largest = left; if (right < heap->size && heap->nodes[right].value > heap->nodes[largest].value) largest = right; if (largest != i) { swap(&heap->nodes[i], &heap->nodes[largest]); heapify(heap, largest); } } // Function to insert a value into the max-heap void insertHeap(MaxHeap *heap, int value) { bool found = false; for (int i = 0; i < heap->size; i++) { if (heap->nodes[i].value == value) { heap->nodes[i].count++; found = true; break; } } if (!found) { heap->nodes[heap->size].value = value; heap->nodes[heap->size].count = 1; heap->size++; } for (int i = heap->size / 2 - 1; i >= 0; i--) heapify(heap, i); } // Function to delete a value from the max-heap void deleteHeap(MaxHeap *heap, int value) { for (int i = 0; i < heap->size; i++) { if (heap->nodes[i].value == value) { heap->nodes[i].count--; if (heap->nodes[i].count == 0) { swap(&heap->nodes[i], &heap->nodes[heap->size - 1]); heap->size--; for (int j = heap->size / 2 - 1; j >= 0; j--) heapify(heap, j); } break; } } } // Function to get the maximum value from the max-heap int getMaxHeap(MaxHeap *heap) { return heap->size > 0 ? heap->nodes[0].value : 0; } int main() { int N; Event events[2 * N]; int eventCount = 0; // Reading input and creating events for (int i = 0; i < N; i++) { int L, R, H; events[eventCount++] = (Event){L, H, 1}; // start of the building events[eventCount++] = (Event){R, H, -1}; // end of the building } // Sorting events MaxHeap *heap = createMaxHeap(2 * N); int prevHeight = 0; for (int i = 0; i < eventCount; i++) { if (events[i].type == 1) { // start of a building insertHeap(heap, events[i].height); } else { // end of a building deleteHeap(heap, events[i].height); } int currentMaxHeight = getMaxHeap(heap); if (currentMaxHeight != prevHeight) { prevHeight = currentMaxHeight; } } return 0; }