Submission

Score: 0

User: qweqwe

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-16 21:21:20

#include <bits/stdc++.h>
#define speed cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<ll,ll>
using namespace std;
int main(){
	//speed;
	ll n,m;cin >> n >> m;
	vector<ll> num(n);
	vector<pii> dp;
	ll mx=0;
	for (int i=0;i<n;i++){
		cin >> num[i];
	}
	vector<ll> temp(m+1,0);
	for (int i=0;i<m;i++){
		ll a,b;cin >> a >> b;
		mx=max(mx,a);
		temp[a]+=b;
	}
	for (int i=0;i<=m;i++){
		dp.push_back(make_pair(i,temp[i]));
	}
	for (int i=1;i<=m;i++){
		dp[i].second=dp[i-1].second+dp[i].second;
	}
	for (int i=0;i<n;i++){
		int val=min(mx,num[i]);
		int l=0,r=m;
		while (l<r){
			//cout << l << " " << r << "\n";
			int mid=(l+r+1)/2;
			if (dp[mid].first==val){
				cout << dp[mid].second << "\n";
				break;
			}else if (dp[mid].first>val){
				r=mid;
			}else if (dp[mid].first<val){
				l=mid;
			}
		}
	}
	/*
	for (pii i:dp){
		cout << i.first << " " << i.second << "\n";
	}
	*/
	return 0;
}