记录编号 203743 评测结果 AAAAAAAAAA
题目名称 平凡的题面 最终得分 100
用户昵称 GravatarChenyao2333 是否通过 通过
代码语言 C++ 运行时间 0.255 s
提交时间 2015-11-03 16:06:05 内存使用 2.60 MiB
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int kN = 2e5+10;
struct Point {
	int x, r;
	int type; // 0 为区间左端点, 1 为点
	bool operator < (const Point & p) const {
		if (x != p.x) return x < p.x;
		else return type < p.type;
	}
}ps[kN];
int N, M;
int main() {
	freopen("bg.in", "r", stdin);
	freopen("bg.out", "w", stdout);
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		int x; scanf("%d", &x);
		ps[i].x = x;
		ps[i].type = 1;
	}
	for (int i = 1; i <= M; i++) {
		int l, r; scanf("%d %d", &l, &r);
		ps[i+N].x = l;
		ps[i+N].r = r;
		ps[i+N].type = 0;
	}
	
	sort(ps+1, ps+1+N+M);
	priority_queue<int> q;
	int ans = 0;
	for (int i = 1; i <= N+M; i++) {
		if (ps[i].type == 0) {
			q.push(-ps[i].r);
		} else {
			int x = ps[i].x;
			while (q.size() && -q.top() < x) {
				q.pop();
			}
			if (q.size()) {
				q.pop();
				ans++;
			}
		}
	}
	
	printf("%d\n", ans);
	return 0;
}