Submission

Score: 100

User: patty

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

Language: cpp

Time: 0.240 second

Submitted On: 2026-03-19 15:11:02

#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() { //normal int
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin >> n >> m;
	vector<int> hero(n);
	for(int i=0;i<n;i++) cin >> hero[i];
	vector<pair<int,int>> monster;
	vector<int> num(m);
	for(int i=0;i<m;i++) {
		int a,b;
		cin >> a >> b;
		monster.push_back({a,b});
	}
	sort(monster.begin(),monster.end());
	for(int i=1;i<m;i++) {
		monster[i].second +=monster[i-1].second;
	}
	for(int i=0;i<m;i++) num[i] = monster[i].first;
//	for(auto i : monster) cout << i.first << ' ' << i.second << '\n';
//	for(auto i : num) cout << i << ' ';
//	map<int,int> dp;
	for(int i=0;i<n;i++) {
//			long long coins = 0;
		pair<int,int> c = {hero[i],LLONG_MAX};
		int u = upper_bound(monster.begin(),monster.end(),c) -monster.begin();
//			int u = upper_bound(num.begin(),num.end(),hero[i]) - num.begin();
//			for(int j=0;j<u;j++) coins+=monster[j].second;
		if(u==0) cout << 0 << '\n';
		else cout << monster[u-1].second << '\n';
//			dp.insert({hero[i],monster[u-1].second});
	}
}