记录编号	159946	评测结果	AAAWWAAWWAWWAA
题目名称	奶牛跑步2	最终得分	57
用户昵称	ggwdwsbs	是否通过	未通过
代码语言	C++	运行时间	0.489 s
提交时间	2015-04-23 12:44:06	内存使用	3.36 MiB

#include<stdio.h>
#include<set>
using namespace std;
struct road
{
	long long data;
	int num;
}c;
struct cmp
{
	bool operator () (const road&a,const road&b)
	{
		return a.data<b.data;
	}
};
set<road,cmp>s;
set<road>::const_iterator it;
const int maxn=100010;
const long long INF=1e18;
long long road[maxn];
long long pos[maxn];
long long v[maxn];
long long end[maxn];
long long t;
int n,num=0;
int main()
{
	freopen("cowjogb.in","r",stdin);
	freopen("cowjogb.out","w",stdout);
	scanf("%d%lld",&n,&t);
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld%lld",&pos[i],&v[i]);
		end[i]=pos[i]+v[i]*t;
	}
	num=0;
	for(int i=n;i>=1;i--)
	{
		c.data=end[i],c.num=0;
		it=s.upper_bound(c);			
		if(it==s.end())
		{
			num++;				
			c.data=end[i],c.num=num;
			s.insert(c);
		}
		else
		{
			s.erase(*it);
			c=*it;
			c.data=end[i];
			s.insert(c);
		}
	}
	printf("%d",num);
}