Submission

Score: 100

User: Aumar

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

Language: cpp

Time: 0.209 second

Submitted On: 2026-02-18 20:55:02

#include <bits/stdc++.h>
using namespace std;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; cin >> n >> m;
    int hero[n];
    for (int i=0; i<n; i++) cin >> hero[i];
    vector<pair<int, int>> monster(m);
    for (int i=0; i<m; i++){
        cin >> monster[i].first >> monster[i].second;
    }
    sort(monster.begin(), monster.end());

    vector<long long> prefix_sum(m);
    prefix_sum[0] = monster[0].second;
    for (int i=1; i<m; i++){
        prefix_sum[i] = prefix_sum[i-1] + monster[i].second;
    }

    vector<int> power(m);
    for (int i=0; i<m; i++){
        power[i] = monster[i].first;
    }

    for (int i=0; i<n; i++){
        
        auto it = upper_bound(power.begin(), power.end(), hero[i]);
        int idx = it - power.begin(); 

        if (idx == 0) {
            cout << 0 << "\n";
        } else {
            cout << prefix_sum[idx - 1] << "\n";
        }
    }

    return 0;
}