比赛 20150423 评测结果 WWWWWWWWWWWWWW
题目名称 奶牛跑步2 最终得分 0
用户昵称 Satoshi 运行时间 1.732 s
代码语言 C++ 内存使用 9.47 MiB
提交时间 2015-04-23 09:42:36
显示代码纯文本
#include <fstream>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in("cowjogb.in");
ofstream out("cowjogb.out");
long long n,t;
long long f[100001]={0},c[100001]={0};
long long ans=1;
int p[100001]={0};
int b[100001]={0};
int maxs[100001][18]={0};
map<long long,int>F;
/*int megersort(int l,int mid,int r)
{
	int i=l,j=mid+1;
	int k=i;
	while(i<=mid&&j<=r)
	{
		if(b[i]>=b[j])
		{
			p[k++]=b[j++];
			ans+=mid-i+1;
		}
		else p[k++]=b[i++];
	}
	while(i<=mid)p[k++]=b[i++];
	while(i<=r)p[k++]=b[i++];
	for(i=l;i<=r;i++)b[i]=p[i];
	return 0;
}
int meger(int l,int r)
{
	if(l==r)return 0;
	int mid=(l+r)>>1;
	meger(l,mid);
	meger(mid+1,r);
	megersort(l,mid,r);
	return 0;
}*/
int main()
{
	int i,j,m=0,l,r,shang;
	long long a,bb,e;
	in>>n>>t;
	for(i=1;i<=n;i++)
	{
		in>>a>>bb;
		f[i]=a+bb*t;
		c[i]=f[i];
	}
	sort(c+1,c+n+1);
	for(i=1;i<=n;i++)
	{
		if(c[i]==c[i+1])
		{
			c[i]=-1;
		}
	}
	for(i=1;i<=n;i++)
	{
		if(c[i]!=-1)
		{
			m++;
			F[c[i]]=m;
		}
	}
	for(i=1;i<=n;i++)
	{
		f[i]=F[f[i]];
		//out<<f[i]<<' ';
		b[i]=f[i];
	}
	for(i=1;i<=n;i++)out<<b[i]<<' ';
	out<<endl;
	for(i=1;i<=n;i++)maxs[i][0]=b[i];
	m=int(trunc(log2(n)));
	for(i=1;i<=m;i++)
	{
		for(j=n;j>=1;j--)
		{
			maxs[j][i]=maxs[j][i-1];
			if(j+(1<<(i-1))<=n)
			{
			    maxs[j][i]=max(maxs[j][i],maxs[j+(1<<i-1)][i-1]);
			}
		}
	}
	for(i=n;i>=2;i--)
	{
		l=1;r=i-1;
		m=int(trunc(log2(r-l+1)));
		shang=max(maxs[l][m],maxs[r-(1<<m)+1][m]);
		//out<<shang<<' ';
		if(shang>=b[i])ans++;
	}
	//for(i=1;i<=n;i++)b[i]=1;
	//meger(1,n);
	//for(i=1;i<=n;i++)out<<p[i]<<' ';
	out<<ans<<endl;
	return 0;
}