Submission

[PP-SSSSSSSSSSSSSSSSS]

Score: 0

User: Pera

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-26 15:54:15

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> findprefsum(vector<pair<int, int>>& arr) {
    int n = arr.size();
    vector<pair<int, int>> prefsum(n);

    prefsum[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        prefsum[i].second = arr[i].second + prefsum[i - 1].second;
        prefsum[i].first = arr[i].first;
    }
    return prefsum;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int heroes, monsters; cin >> heroes >> monsters;
    vector<int> power(heroes);
    for (int i = 0; i < heroes; ++i) {
        cin >> power[i];
    }
    vector<pair<int, int>> hp(monsters);
    for (int i = 0; i < monsters; ++i) {
        cin >> hp[i].first >> hp[i].second;
    }

    sort(hp.begin(), hp.end(), [](pair<int, int>& a, pair<int, int>& b) {
        return a.first < b.first;
    });

    vector<pair<int, int>> prefixsum = findprefsum(hp);

    for (int i = 0; i < heroes; ++i) {
        int p = power[i];

        int low = 0;
        int high = monsters - 1;

        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (prefixsum[mid].first <= p) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        // no monster beaten
        if (high < 0) {
            cout << 0 << '\n';
            continue;
        }

        cout << prefixsum[high].second << '\n';
    }
}