记录编号	159971	评测结果	AAAAAAAAAAAAAA
题目名称	奶牛跑步2	最终得分	100
用户昵称	TAT	是否通过	通过
代码语言	C++	运行时间	0.614 s
提交时间	2015-04-23 14:40:53	内存使用	0.95 MiB

#include<cstdio>
#include<cstdlib>
struct node{
	node *c[2];
	int val,siz;
	long long key;
	node(){
        key=val=siz=0;
		c[0]=c[1]=NULL;
	}
	void update(){
		siz=c[0]->siz+c[1]->siz+1;
	}
	node(const long long &x);
};
node *Null=new node,*root=Null,*tmp;
node::node(const long long &x){
	key=x,val=rand(),siz=1;
	c[0]=c[1]=Null;
}
void rot(node *&o,const bool &d){
	tmp=o->c[!d],o->c[!d]=tmp->c[d],tmp->c[d]=o;
	tmp->siz=o->siz,o->update(),o=tmp;
}
void ins(node *&o,const long long &x){
	if(o==Null){
		o=new node(x);
		return;
	}
	bool d=(x>=o->key);
	ins(o->c[d],x),o->siz++;
	if(o->c[d]->val<o->val) rot(o,!d);
}
void del(node *&o,const long long &x){
	if(o->key==x){
		if(o->c[0]==Null) {o=o->c[1];return;}
		if(o->c[1]==Null) {o=o->c[0];return;}
		bool d=(o->c[0]->val<o->c[1]->val);
		rot(o,d),del(o->c[d],x);
	}
	else del(o->c[(x>=o->key)],x);
	o->siz--;
}
long long suc(const long long &x){
	static long long res;
	res=-1,tmp=root;
	while(tmp!=Null){
		if(tmp->key>x) res=tmp->key,tmp=tmp->c[0];
		else tmp=tmp->c[1];
	}
	return res;
}
int main(){
    freopen("cowjogb.in","r",stdin);
	freopen("cowjogb.out","w",stdout);
	srand(19990214);
	int n,v,m=0;
	long long t,p[100000];
	scanf("%d%lld",&n,&t);
	for(int i=0;i<n;i++)
	    scanf("%lld%d",&p[i],&v),p[i]+=t*v;
	for(int i=n-1;~i;i--){
		long long now=suc(p[i]);
		if(now!=-1) del(root,now);
		else m++;
		ins(root,p[i]);
	}
	printf("%d\n",m);
	return 0;
}