1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5    int *item1 = *(int **)a;
6    int *item2 = *(int **)b;
7    if (item1[0] == item2[0]) return item2[1] - item1[1];
8    return item1[0] - item2[0];
9}
10
11int binarySearch(int *prices, int *beauties, int left, int right, int query) {
12    int answer = 0;
13    while (left <= right) {
14        int mid = left + (right - left) / 2;
15        if (prices[mid] <= query) {
16            answer = beauties[mid];
17            left = mid + 1;
18        } else {
19            right = mid - 1;
20        }
21    }
22    return answer;
23}
24
25int* maxBeautyForQueries(int **items, int itemsSize, int *itemsColSize, int *queries, int queriesSize, int *returnSize) {
26    qsort(items, itemsSize, sizeof(int *), compare);
27    int *prices = (int *)malloc(sizeof(int) * itemsSize);
28    int *beauties = (int *)malloc(sizeof(int) * itemsSize);
29    int currentMaxBeauty = 0;
30
31    for (int i = 0; i < itemsSize; i++) {
32        currentMaxBeauty = currentMaxBeauty > items[i][1] ? currentMaxBeauty : items[i][1];
33        prices[i] = items[i][0];
34        beauties[i] = currentMaxBeauty;
35    }
36
37    int *result = (int *)malloc(sizeof(int) * queriesSize);
38    for (int i = 0; i < queriesSize; i++) {
39        result[i] = binarySearch(prices, beauties, 0, itemsSize - 1, queries[i]);
40    }
41
42    free(prices);
43    free(beauties);
44    *returnSize = queriesSize;
45    return result;
46}
47
48int main() {
49    int *items[] = { (int[]){1, 2}, (int[]){3, 2}, (int[]){2, 4}, (int[]){5, 6}, (int[]){3, 5} };
50    int queries[] = {1, 2, 3, 4, 5, 6};
51    int itemsSize = 5;
52    int queriesSize = 6;
53    int itemsColSize = 2;
54    int returnSize;
55    int *result = maxBeautyForQueries(items, itemsSize, &itemsColSize, queries, queriesSize, &returnSize);
56    for (int i = 0; i < returnSize; i++) {
57        printf("%d ", result[i]);
58    }
59    free(result);
60    return 0;
61}