Submission

Score: 100

User: tha_smith

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

Language: cpp

Time: 0.215 second

Submitted On: 2026-03-07 15:10:36

#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<pair<ll,ll>> c(M);
	vector<ll> p(M),h(N),ans(N),pf(M);
	
	for(ll i=0; i<N; i++)
		cin >> h[i];
	for(ll i=0; i<M; i++)
		cin >> c[i].first >> c[i].second;
	sort(c.begin(),c.end());
	
	for(ll i=0; i<M; i++)
		p[i] = c[i].first;
	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(p.begin(),p.end(),h[i])-p.begin()-1;
		if(idx<0)
			continue;
		ans[i]=pf[idx];
	}
	for(ll i=0; i<N; i++)
		cout << ans[i] << '\n';
}