Submission

Score: 100

User: letdown

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

Language: cpp

Time: 0.234 second

Submitted On: 2026-03-12 13:17:53

#include <bits/stdc++.h>

#define int long long
using namespace std;
signed main() {
    cin.tie(NULL)->sync_with_stdio(0);
    int n, m, p, c;
    cin >> n >> m;

    int h[n], ans[n], dp[m];
    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < m; i++) {
        cin >> p >> c;
        v.push_back({p, c});
    }

    sort(v.begin(), v.end());

    dp[0] = v[0].second;
    for (int i = 1; i < m; i++) dp[i] = dp[i-1] + v[i].second;

    for (int i = 0; i < n; i++) {
        auto it = upper_bound(v.begin(), v.end(), pair<int, int>(h[i], INT_MAX));
        if (it == v.begin()) {
            ans[i] = 0;
            continue;
        }
        it--;

        ans[i] = dp[it - v.begin()];
    }

    for (auto i : ans) cout << i << "\n";
}