Submission

Score: 100

User: Quaoar

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

Language: cpp

Time: 0.239 second

Submitted On: 2026-02-28 23:40:42

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <utility>
#include <climits>
using namespace std;
using ll = long long;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , m;
    cin >> n >> m;
    ll power[200000];
    vector <ll> sum;
    vector<pair <ll , ll>> mp;
    vector <ll> pos;
    for (int i = 0 ; i < n ; i++){
        cin >> power[i];
    }

    for (int i = 0 ; i < m ; i++){
        int a , b;
        cin >> a >> b;
        mp.push_back(make_pair(a, b));
    }
    sort(mp.begin() , mp.end());
    /*
    for (auto i : mp){
        cout << i.first << " " << i.second << "\n";
    }
    */
    for (int i = 0 ; i < n ; i++){
        auto it = upper_bound(mp.begin() , mp.end() , make_pair((ll)power[i], LLONG_MAX));
        ll t = it - mp.begin();
        pos.push_back(t);
    }
    /*
    for (auto i : pos){
        cout << i << "\n";
    }
    */
    ll s = 0;
    for (int i = 0 ; i < mp.size() ; i++){
        s = s + mp[i].second;
        sum.push_back(s);
    }
    for (int i = 0 ; i < n ; i++){
        if (pos[i] == 0){
            cout << 0 << "\n";
        } else {
            cout << sum[--pos[i]] << "\n";
        }
    }
    
    return 0;
}