Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Cmoss9

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

Language: cpp

Time: 0.238 second

Submitted On: 2025-04-01 00:41:19

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

int main () {
    cin.tie(0) -> sync_with_stdio(0);
    int n,m;
    cin >> n >> m;
    vector<int> power(n);
    for (int i = 0;i<n;i++) {
        cin >> power[i];
    }
    vector<pair<int,int>> monster;
    for (int i = 0;i<m;i++) {
        int a,b;
        cin >> a >> b;
        monster.push_back(make_pair(a,b));
    }

    vector<long long> result;
    result.reserve(n);

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

    vector<long long> prefix(m+1, 0);
    for (int i = 0; i < m; i++) {
        prefix[i+1] = prefix[i] + monster[i].second;
    }

    for (int i = 0;i<n;i++) {
        int str = power[i];
        auto it = upper_bound(monster.begin(),monster.end(),make_pair(str, INT_MAX),
        [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first < b.first;
        });
        int dis = distance(monster.begin(),it);
        long long res = prefix[dis];
        result.push_back(res);
    }

    for (auto i : result) {
        cout << i << '\n';
    }

}

/*
4 5
1 4 2 6
1 2
1 3
5 4
2 5
3 6
ans
5
16
10
20
*/