Submission

Score: 100

User: tha_smith

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

Language: cpp

Time: 0.214 second

Submitted On: 2026-02-27 16:31:31

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

int main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	ll N,M;
	cin >> N >> M;
	vector<ll> h(N),ans(N);
	for(ll i=0; i<N; i++) {
		cin >> h[i];
	}
	
	vector<pair<ll,ll>> c(M);
	for(ll i=0; i<M; i++) {
		cin >> c[i].first >> c[i].second;
	}
	sort(c.begin(),c.end());
	
	vector<ll> pow(M);
	for(ll i=0; i<M; i++) {
		pow[i] = c[i].first;
	}
	
	vector<ll> pf(M);
	pf[0] = c[0].second;
	for(ll i=1; i<M; i++) {
		pf[i] = pf[i-1]+c[i].second;
	}
	
	for(ll i=0; i<N; i++) {
		int idx = upper_bound(pow.begin(),pow.end(),h[i])-pow.begin()-1;
		if(idx<0)
			continue;
		ans[i] = pf[idx];
	}
	
	for(ll i=0; i<N; i++) {
		cout << ans[i] << '\n';
	}
}