Submission

Score: 100

User: Nagornz

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

Language: cpp

Time: 0.228 second

Submitted On: 2025-11-04 06:53:34

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

int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);

    // input
    int n, m;
    cin >> n >> m;
    vector <int> a(n), ans(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector <pair <int, int>> mon(m);
    for (int i = 0; i < m; i++) {
        cin >> mon[i].first >> mon[i].second; // P[i], C[i]
    }

    sort(mon.begin(), mon.end()); // เรียงช้อมูลตามค่า P

    vector <int> power(m);
    for (int i = 0; i < m; i++) {
        power[i] = mon[i].first; // ดึงค่า P มาเก็บใน Array ใหม่
    }

    // Prefix Sum ของ C[i]
    vector <int> pref(m);
    pref[0] = mon[0].second;
    for (int i = 1; i < m; i++) {
        pref[i] = pref[i - 1] + mon[i].second;
    }

    // หาคำตอบของฮีโร่แต่ละคนโดยการใช้ Binary Search
    for (int i = 0; i < n; i++) {
        int idx = upper_bound(power.begin(), power.end(), a[i]) - power.begin() - 1; // หา index (ในที่นี้ ตั้งชื่อว่า idx)
        if (idx < 0) continue; // idx < 0 นั่นคือ ฮีโร่คนที่ i ไม่สามารถชนะมอนสเตอร์ตัวไหนได้เลย
        ans[i] = pref[idx]; // คำตอบของฮีโร่คนที่ i คือ pref[idx]
    }

    // Output
    for (int i = 0; i < n; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}