Submission

Score: 100

User: goine

Problemset: ฮีโร่และมอนสเตอร์

Language: cpp

Time: 0.225 second

Submitted On: 2026-03-11 10:18:19

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int hero_count, monster_count;
    cin >> hero_count >> monster_count;

    vector<int> heroes(hero_count);
    for (int &h : heroes) cin >> h;

    vector<pair<int,int>> monsters(monster_count);
    for (auto &m : monsters) cin >> m.first >> m.second;

    if (monster_count == 0) {
        for (int i = 0; i < hero_count; i++) cout << 0 << " ";
        return 0;
    }

    sort(monsters.begin(), monsters.end());

    vector<long long> pref(monster_count);
    pref[0] = monsters[0].second;
    for (int i = 1; i < monster_count; i++)
        pref[i] = pref[i-1] + monsters[i].second;

    for (int h : heroes) {
        auto it = upper_bound(monsters.begin(), monsters.end(),
                              make_pair(h, INT_MAX));

        if (it == monsters.begin()) {
            cout << 0 << '\n';
        } else {
            int pos = prev(it) - monsters.begin();
            cout << pref[pos] << '\n';
        }
    }

    return 0;
}