比赛 20150423 评测结果 AAAWWAAWWAWWAA
题目名称 奶牛跑步2 最终得分 57
用户昵称 ggwdwsbs 运行时间 0.614 s
代码语言 C++ 内存使用 3.36 MiB
提交时间 2015-04-23 11:14:35
显示代码纯文本
#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;
	}
	if(n<=2500)
	{
		num=0;
		for(int i=n;i>=1;i--)
		{
			long long min=INF;
			int poss=0;
			for(int j=1;j<=num;j++)
			 if(road[j]>end[i]&&road[j]-end[i]<min)
			 {
			 	min=road[j]-end[i];
			 	poss=j;
			 }
			if(min==INF) num++,road[num]=end[i];
			else road[poss]=end[i];
		}
		printf("%d",num);
	}
	else
	{
		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);
	}	
}