2838. Maximum Coins Heroes Can Collect

There is a battle and n heroes are trying to defeat m monsters. You are given two 1-indexed arrays of positive integers heroes and monsters of length n and m, respectively. heroes[i] is the power of ith hero, and monsters[i] is the power of ith monster.

The ith hero can defeat the jth monster if monsters[j] <= heroes[i].

You are also given a 1-indexed array coins of length m consisting of positive integers. coins[i] is the number of coins that each hero earns after defeating the ith monster.

Return an array ans of length n where ans[i] is the maximum number of coins that the ith hero can collect from this battle.

Notes

• The health of a hero doesn’t get reduced after defeating a monster.
• Multiple heroes can defeat a monster, but each monster can be defeated by a given hero only once.

class Solution {
public:
    vector<long long> maximumCoins(vector<int>& heroes, vector<int>& monsters, vector<int>& coins) {
        vector<pair<long long, long long>> S;
        for(int i = 0; i < monsters.size(); i++) {
            S.push_back({monsters[i], coins[i]});
        }
        sort(begin(S), end(S));
        for(int i = 1; i < S.size(); i++) {
            S[i].second += S[i-1].second;
        }
        vector<long long> res;
        long long inf = 1e18;
        for(auto& h : heroes) {
            auto p = upper_bound(begin(S), end(S), make_pair(1ll * h,inf)) - begin(S) - 1;
            res.push_back(p == -1 ? 0 : S[p].second);
        }
        return res;
    }
};