记录编号	398384	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	0.782 s
提交时间	2017-04-22 10:06:55	内存使用	92.02 MiB

#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

#define MAXN 10000005
#define MAXM 1005

int N, M;

bool vis[MAXM];

int L[MAXN], R[MAXN];
int id = 1, G[2*MAXM][2*MAXM], Len[2*MAXM];

priority_queue<int> Q, Qdel;

int main() {
	freopen("ha14d.in", "rt", stdin);
	freopen("ha14d.out", "wt", stdout);
	
	int i, k, x, y, a, b;
	scanf("%d%d", &N, &M);
	for(i=1;i<=M;i++) {
		scanf("%d%d", &x, &y);
		if(!(a = L[x])) a = (L[x] = id++);
		if(!(b = R[y])) b = (R[y] = id++);
		
		G[ a ][ Len[a]++ ] = i;
		G[ b ][ Len[b]++ ] = i;
	}
	
	for(i=1;i<=N;i++) {
		//set in L
		a = L[i];
		for(k=0;k<Len[a];k++) Q.push(G[a][k]);
		
		while(!Qdel.empty() && !Q.empty() && Q.top() == Qdel.top()) {
			Q.pop(); Qdel.pop();
		}
		
		if(!Q.empty()) vis[Q.top()] = 1;
		
		//get out R
		b = R[i];
		for(k=0;k<Len[b];k++) Qdel.push(G[b][k]);
	}
	
	int Ans = 0;
	for(i=1;i<=M;i++) if(vis[i]) Ans++;
	printf("%d\n", Ans);
}