记录编号	99407	评测结果	AAAAAAAAAA
题目名称	[Vijos 1291] 苹果摘陶陶	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-04-27 20:53:48	内存使用	0.35 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>

using namespace std;
#define N 2100
struct TREAP{
	struct arr{
		int l,r,dat;
		int ran;
	}t[N];
	int root,size;
	void clean(){
		memset(t,0,sizeof(t));
		size = root = 0;
	}
	void right(int &x){
		int tem = t[x].r;
		t[x].r = t[tem].l;
		t[tem].l = x;
		x = tem;
		return;
	}
	void left(int &x){
		int tem = t[x].l;
		t[x].l = t[tem].r;
		t[tem].r = x;
		x = tem;
		return;
	}
	
	void insert(int &x,int y){
		if (! x){
			x = ++ size;
			t[x].l = t[x].r = 0;
			t[x].dat = y;
			t[x].ran = rand();
		}
		else{
			if (t[x].dat > y){
				insert(t[x].l,y);
				if (t[x].ran > t[t[x].l].ran) left(x);
			}
			else{
				insert(t[x].r,y);
				if (t[x].ran > t[t[x].r].ran) right(x);
			}
		}
		return;
	}
	int askpre(int x,int y){
		if (!x) return -1;
		int ans = -1;
		if (t[x].dat >= y){
			ans = max(ans,askpre(t[x].l,y));
		}
		else{
			ans = max(t[x].dat,askpre(t[x].r,y));
		}
		return ans;
	} 
	
	void del(int & x,int y){
		if (t[x].dat == y){
			if (t[x].l == 0 || t[x].r == 0){
				if (t[x].l == 0){
					x = t[x].r;
					return;
				}
				else{
					x = t[x].l;
					return;
				}
				
			}
			else{
				if (t[t[x].r].ran > t[t[x].l].ran){
					left(x);
					del(t[x].r,y);
				}
				else{
					right(x);
					del(t[x].l,y);
				}
			}
		}
		else{
			if (t[x].dat > y){
				del(t[x].l,y);
			}
			else del(t[x].r,y);
		}	
	}
	
}T;
int n,m;
int a[N];
int main(){
	freopen("applea.in","r",stdin);
	freopen("applea.out","w",stdout);
	T.clean();
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i++) scanf("%d",&a[i]);	
	int x;
	for (int i = 1; i <= m; i++){
		scanf("%d",&x);
		if (x > 0) T.insert(T.root,x);
	}
	int tem;
	for (int i = 1; i <= n; i++){
		tem = T.askpre(T.root,a[i]);
		if (tem > 0){
			--m;
			T.del(T.root,tem);
		}
	}
	printf("%d\n",m);
	return 0;
}