C++ 排序+ 二分查找

#include <iostream>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <stack>
#include <queue>
#include <stdio.h>

using namespace std;

struct Job {
	int d, p;
	Job(int d, int p) : d(d), p(p) {}
	bool operator < (const Job& other) {
		return d < other.d;
	}
};

int process(vector<Job>& jobs, vector<int>& ds, vector<int>& max_ps) {
	sort(jobs.begin(), jobs.end());
	int mx = 0;
	for (auto& job : jobs) {
		mx = max(mx, job.p);
		if (ds.empty() || ds.back() < job.d) {
			ds.push_back(job.d);
			max_ps.push_back(mx);
		} else {
			max_ps.back() = mx;
		}
	}
	return 0;
}

int query(int a, const vector<int>& ds, const vector<int>& max_ps) {
	int k = lower_bound(ds.begin(), ds.end(), a + 1) - ds.begin() - 1;
	if (k < 0) return 0;
	return max_ps[k];
}

int main() {
	int N, M;
	cin >> N >> M;
	vector<Job> jobs;
	int d, p;
	for (int i = 0; i < N; ++i) {
		cin >> d >> p;
		jobs.push_back(Job(d, p));
	}
	
	vector<int> ds;
	vector<int> max_ps;
	process(jobs, ds, max_ps);

	int a;
	for (int i = 0; i < M; ++i) {
		cin >> a;
		cout << query(a, ds, max_ps) << endl;
	}
    return 0;
}