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 |
Source Code
#include <stdio.h> #include <stdlib.h> #include <limits.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 two events have the same x-coordinate, prioritize the start of a building over the end of a building return (event1->type * event1->height) - (event2->type * event2->height); } // A utility function to swap two elements void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // Max-heap implementation void heapify(int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { swap(&arr[i], &arr[largest]); heapify(arr, n, largest); } } void insertHeap(int heap[], int* size, int value) { heap[*size] = value; (*size)++; for (int i = (*size) / 2 - 1; i >= 0; i--) heapify(heap, *size, i); } void deleteHeap(int heap[], int* size, int value) { int i; for (i = 0; i < *size; i++) { if (heap[i] == value) break; } swap(&heap[i], &heap[*size - 1]); (*size)--; for (int i = (*size) / 2 - 1; i >= 0; i--) heapify(heap, *size, i); } int getMaxHeap(int heap[], int size) { return size > 0 ? heap[0] : 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 int maxHeap[2 * N]; int heapSize = 0; int prevHeight = 0; for (int i = 0; i < eventCount; i++) { if (events[i].type == 1) { // start of a building insertHeap(maxHeap, &heapSize, events[i].height); } else { // end of a building deleteHeap(maxHeap, &heapSize, events[i].height); } int currentMaxHeight = getMaxHeap(maxHeap, heapSize); if (currentMaxHeight != prevHeight) { prevHeight = currentMaxHeight; } } return 0; }