Submission

Score: 100

User: Shangbin

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

Language: cpp

Time: 0.211 second

Submitted On: 2026-03-10 09:33:38

//Problem = https://grader.gchan.moe/problemset/c2_st66_heroes/statement
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll maxn = 2e5 + 5, maxm = 8e5 + 5, inf = 4e18;
ll n, m, h[maxn];

//O(m + n log m)

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n >> m;
    vector<pair<ll, ll>> pc(m);
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < m; i++) cin >> pc[i].first >> pc[i].second;
    sort(pc.begin(), pc.end());
    for (int i = 1; i < m; i++) pc[i].second += pc[i - 1].second; //Presum
    for (int i = 0; i < n; i++){
        auto it = upper_bound(pc.begin(), pc.end(), make_pair(h[i], inf)) - 1;
        if (it >= pc.begin())
            cout << it->second << '\n';
        else 
            cout << "0\n"; 
    }
}