Submission

Score: 100

User: mantaggez

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

Language: cpp

Time: 0.585 second

Submitted On: 2026-03-12 16:52:11

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

const ll nx = 2e5+5;
const ll mx = 8e5+5;

ll n, m, h[nx];
vector<ll> idx;
vector<pii> mon;
map<ll, ll> mp;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    for(ll i=1;i<=n;i++) cin >> h[i];
    for(ll i=1;i<=m;i++)
    {
        ll p, c;
        cin >> p >> c;
        idx.push_back(p);
        mon.push_back({p, c});
    }

    sort(idx.begin(), idx.end());
    // idx.erase(unique(idx.begin(), idx.end()), idx.end());
    sort(mon.begin(), mon.end());

    ll cur = 0;
    for(auto& [p, c] : mon)
    {
        cur += c;
        mp[p] = cur;
    }

    for(ll i=1;i<=n;i++)
    {
        auto it = upper_bound(idx.begin(), idx.end(), h[i]);
        if(it == idx.begin()) cout << 0 << '\n';
        else it--, cout << mp[*it] << '\n';
    }

    return 0;
}