Submission

Score: 0

User: faofao

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-13 17:25:36

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN = 200005 ;
const int mxM = 800005 ;
ll power[mxN] ;
ll reward[mxN] ;
vector<pair<ll,ll>> monster ;
vector<ll> pref;
vector<ll> k;
int n,m ;

int main(){
    int n,m ; cin >> n >> m ;
    for(int i=0 ; i<n ; i++) cin >> power[i] ;
    for(int i=0 ; i<m ; i++){
        ll p,c ; cin >> p >> c ;
        monster.push_back({p,c}) ;
    }
    sort(monster.begin(),monster.end()) ;
    k.resize(m) ;
    pref.resize(m) ;
    //prefix sum ?
    k[0] = monster[0].first;
    pref[0] = monster[0].second;

    for(int i=1 ; i<m ; i++){
        k[i] = monster[i].first ;
        pref[i] = pref[i-1] + monster[i].second ;
    }

    for(int i=0 ; i<n ;i++){
        int cost = upper_bound(k.begin(),k.end(),power[i])-k.begin() -1;
        cout << pref[cost] << "\n" ;
    }
}