Submission

Score: 0

User: Nathako9n

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

Language: cpp

Time: 0.050 second

Submitted On: 2026-02-08 10:57:05

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

int n, m;
const int N = 200005;
ll ar[N+4];
pair<ll, ll> br[N+3];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> ar[i];
    for (int i = 1; i <= m; i++) cin >> br[i].first >> br[i].second;

    sort(br + 1, br + m + 1);

    // Prefix sum of the values
    for (int i = 1; i <= m; i++) br[i].second += br[i-1].second;

    for (int i = 1; i <= n; i++) {
        // Find first element > ar[i]. We use a very large second value to act as infinity.
        auto it = upper_bound(br + 1, br + m + 1, make_pair(ar[i], (ll)2e18));

        // Move back one to get the sum of all elements <= ar[i]
        cout << prev(it)->second << endl;
    }
    return 0;
}