Submission

Score: 100

User: qweqwe

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

Language: cpp

Time: 0.798 second

Submitted On: 2025-10-16 21:43:52

#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;

map<ll,ll> temp;

int main(){
	speed;
	ll n,m;cin >> n >> m;
	vector<ll> num(n);
	vector<pii> dp;
	ll mx=0,mn=1e15;
	for (int i=0;i<n;i++){
		cin >> num[i];
	}
	for (int i=0;i<m;i++){
		ll a,b;cin >> a >> b;
		temp[a]+=b;
	}
	ll sum=0;
	for (pii i:temp){
		sum+=i.second;
		dp.push_back(make_pair(i.first,sum));
	}int o=dp.size();
	for (int i=0;i<n;i++){
		ll val=num[i];
		ll l=0,r=o-1;
		if (val<dp[0].first){
			cout << 0 << "\n";
			continue;
		}else if (val>=dp[o-1].first){
			cout << dp[o-1].second << "\n";
			continue;
		}
		while (l<r){
			//cout << l << " " << r << "\n";
			ll mid=(l+r+1)/2;
			if (dp[mid].first==val){
				l=mid;break;
			}else if (dp[mid].first<=val){
				l=mid;
			}else if (dp[mid].first>val){
				r=mid-1;
			}
		}
		cout << dp[l].second << "\n";
	}
	/*
	for (pii i:dp){
		cout << i.first << " " << i.second << "\n";
	}
	*/
	return 0;
}