C++ || My Approach(Still finding a way to find solution usin C)
Intuition\n- To find the maximum sum for each query, we can iterate through the elements of nums1 in descending order and maintain a monotonically decreasing st
# Intuition\n- To find the maximum sum for each query, we can iterate through the elements of nums1 in descending order and maintain a monotonically decreasing stack. The stack will store pairs of values where the first element is from nums2 and the second element is the sum of corresponding elements from nums1 and nums2. By doing so, we can efficiently find the maximum sum for each query using binary search.\n# Approach\n1. Sort the indices of nums1 in descending order based on their corresponding values. This will allow us to iterate through nums1 in descending order efficiently.\n2. Sort the indices of queries in descending order based on the first element of each query. This will allow us to process queries in descending order of the required condition.\n3. Initialize an empty stack (st) to maintain the monotonically decreasing values.\n4. Iterate through the queries and perform the following steps:\n- Retrieve the current query queries[i_query].\n- Iterate through the remaining elements of nums1 starting from the current index j and perform the following steps:\n- Retrieve the current element values num1 and num2 from nums1 and nums2 using the sorted indices.\n- Remove elements from the stack (st) that are not useful for the current query by checking if their sum (second value of the pair) is less than or equal to num1 + num2.\n- If the stack (st) is empty or the top element\'s first value (nums2 value) is less than num2, then push the current pair (num2, num1 + num2) to the stack.\n- Use binary search (lower_bound) on the stack (st) to find the first element with a first value greater than or equal to the second element (q_num2) of the current query.\n- If a valid pair is found, assign its second value as the result for the current query. Otherwise, assign -1 to indicate that no valid pair was found.\n5. Return the resulting vector ret containing the maximum sums for each query.\n# Complexity\n- Time complexity:\nO((n + q)logn + qlogq)\n- Space complexity:\nO(n)\n# Code\n```\n/**\n * Time Complexity: O(n * log(n) + n_queries * log(n_queries) + n_queries * log(n))\n * Space Complexity: O(n + n_queries)\n * where `n` is the length of the vector `nums1`\n *       `n_queries` is the length of the vector `queries`\n */\n/**\n * Time Complexity: O(n * log(n) + n_queries * log(n_queries) + n_queries * log(n))\n * Space Complexity: O(n + n_queries)\n * where `n` is the length of the vector `nums1`\n *       `n_queries` is the length of the vector `queries`\n */\nclass Solution {\nprivate:\n  using st_node_t = pair<int, int>;\n  \n  static constexpr int cant_find = -1;\n  \npublic:\n  vector<int> maximumSumQueries(const vector<int> &nums1,\n                                const vector<int> &nums2,\n                                const vector<vector<int>> &queries) {\n    const int n = static_cast<int>(nums1.size());\n    int indices1[n];\n    iota(indices1, indices1 + n, 0);\n    sort(indices1, indices1 + n, [&nums1](const int lhs, const int rhs) -> bool {\n      return nums1[lhs] > nums1[rhs];\n    });\n    \n    const int n_queries = static_cast<int>(queries.size());\n    int indices_q[n_queries];\n    iota(indices_q, indices_q + n_queries, 0);\n    sort(indices_q, indices_q + n_queries, [&queries](const int lhs, const int rhs) -> bool {\n      return queries[lhs].front() > queries[rhs].front();\n    });\n    \n    vector<int> ret(n_queries, cant_find);\n    vector<st_node_t> st;\n    for (int j = 0, i = 0; i < n_queries; ++i) {\n      const int i_query = indices_q[i];\n      const int q_num1 = queries[i_query].front();\n      const int q_num2 = queries[i_query].back();\n      for (; j < n && nums1[indices1[j]] >= q_num1; ++j) {\n        const int num1 = nums1[indices1[j]];\n        const int num2 = nums2[indices1[j]];\n        while (!st.empty() && st.back().second <= num1 + num2) {\n          st.pop_back();\n        }\n        if (st.empty() || st.back().first < num2) {\n          st.emplace_back(num2, num1 + num2);\n        }\n      }\n      auto lb = lower_bound(st.begin(), st.end(), make_pair(q_num2, 0));\n      ret[i_query] = lb == st.end() ? cant_find : lb->second;\n    }\n    return ret;\n  }\n};\n\n```
['C++']