比赛 |
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;
}