Submission

Score: 100

User: s0m30n3

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

Language: cpp

Time: 0.770 second

Submitted On: 2026-03-18 20:05:05

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<ll> heros(n);
    for(int i=0;i<n;i++){cin>>heros[i];}
    map<ll,ll> monster;
    for(int i=0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        monster[a]+=b;
    }
    vector<pair<ll,ll>> pf;
    ll c=0;
    for(auto [u,v] : monster){
        c+=v;
        pf.push_back({u,c});
    }

    for(int i=0;i<n;i++){
        ll h = heros[i];
        auto it = upper_bound(pf.begin(), pf.end(), make_pair(h, -1LL), [](auto &a, auto &b){
            return a.first<b.first;
        });
        int d = distance(pf.begin(), it);
        if(d<1){
            cout << "0\n";
        }
        else{
        cout << pf[d-1].second << '\n';
        }
    }
}