leetcode

0

1 // Ordered Query

2 class Solution {

3 public:

4 vector<int> maximumBeauty(vector<vector<int>> &items, vector<int> &queries) {

5 static int maxi[100001] = {0};

6 const int n = size(items);

7

8 sort(begin(items), end(items), [](auto &a, auto &b) { return a[0] < b[0]; });

9

10 vector<int> keys = {0};

11 keys.reserve(n);

12

13 for (int i = 0, prev = -1; i < n; i++) {

14 if (items[i][0] != prev) {

15 keys.push_back(prev = items[i][0]);

16 maxi[size(keys)] = maxi[size(keys) - 1];

17 }

18 maxi[size(keys)] = max(maxi[size(keys)], items[i][1]);

19 }

20

21 for (auto &query : queries) {

22 const auto it = upper_bound(begin(keys), end(keys), query);

23 const auto idx = distance(begin(keys), it);

24 query = maxi[idx];

25 }

26

27 return queries;

28 }

29 };

30

31 // Offline Query

32 class Solution {

33 public:

34 vector<int> maximumBeauty(vector<vector<int>> &items, vector<int> &queries) const {

35 static int idxes[100001] = {0};

36 const int n = size(items), m = size(queries);

37

38 iota(idxes, idxes + m, 0);

39 sort(idxes, idxes + m, [&](int a, int b) { return queries[a] < queries[b]; });

40 sort(begin(items), end(items), [](auto &a, auto &b) { return a[0] < b[0]; });

41

42 int maxi = 0, idx = 0;

43 for (int i = 0, prev = -1; i < n; i++) {

44 const int price = items[i][0], value = items[i][1];

45

46 if (price != prev) {

47 while (idx < m && queries[idxes[idx]] < price)

48 queries[idxes[idx++]] = maxi;

49 if (idx == m) break;

50 prev = price;

51 }

52

53 maxi = max(maxi, value);

54 }

55 while (idx < m)

56 queries[idxes[idx++]] = maxi;

57

58 return queries;

59 }

60 };