bzoj3888【Usaco2015 Jan】Stampede

卫子平

2023-12-01

3888: [Usaco2015 Jan]Stampede

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 165 Solved: 55
[ Submit][ Status][ Discuss]

Description

Farmer John's N cows (1 <= N <= 50,000) appear to be stampeding along the road at the front of FJ's farm, but they are actually just running in a foot race to see which cow is the fastest. Viewed from above, each cow is represented by a unit-length horizontal line segment, specified by the coordinates of its left corner point at time t=0. For example, (-3,6) would specify a cow who at time t=0 is represented by the segment from (-3,6) to (-2,6). Each cow is moving to the right (in the +x direction) at a certain rate, specified by the integer amount of time it takes her to move 1 unit to the right. FJ is not particularly thrilled that his cows are outside running instead of in the barn producing milk. He plans to admonish them with a stern lecture after the race ends. In order to determine which of his cows are participating in the race, FJ situates himself at (0,0) and looks along a ray extending in the +y direction. As the race unfolds, FJ sees a cow if she is ever the first cow visible along this ray. That is, a cow might not be visible if another cow is "in front" of her during the entire time she crosses FJ's line of sight. Please compute the number of cows FJ can see during the entire race.
PoPoQQQ站在原点上向y轴正半轴看，然后有一群羊驼从他眼前飞过。这些羊驼初始都在第二象限，尾巴在(Xi,Yi)，头在(Xi+1,Yi)，每Ci秒向右走一个单位。 PoPoQQQ能看见一匹羊驼当且仅当它身体任意某部位x坐标为0时，没有其它y坐标小于此羊驼的羊驼身体某部位x坐标为0。问PoPoQQQ能看见几匹羊驼？

Input

The first line of the input contains N. Each of the following N lines describes a cow with three integers x y r, corresponding to a cow whose left endpoint is at (x,y) at time t=0, moving to the right at a continuous speed of 1 unit of distance every r units of time. The value of x is in the range -1000..-1, the value of y is in the range 1..1,000,000 (and distinct for every cow, to prevent any possible collisions), and the value of r is in the range 1..1,000,000.

Output

A single integer, specifying the number of cows FJ can see during the entire race (from t=0 onward).

Sample Input

3
-2 1 3
-3 2 3
-5 100 1

Sample Output

2

SOLUTION NOTES:

FJ can see cows 1 and 2 but not cow 3.

HINT

Source

Silver&鸣谢PoPoQQQ

离散化+线段树

计算每头牛头和尾经过y轴的时间，用时间轴上的区间记录。将每个区间按纵坐标从小到大排序，依次判断每个区间是否有空白，并将整个区间覆盖，如果有空白就把答案加1。

具体实现时为了使一个点表示一个时间段而不是一个时间点，可以将每一个区间的右端点左移一个单位。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i<=n;i++)
#define LL long long
#define MAXN 50050
using namespace std;
struct cow_type
{
	int l,r,p,c;
}a[MAXN];
struct tree_type
{
	int l,r;
	bool f;
}t[MAXN*8];
int n,x,cnt=0,ans=0,s=0,f[MAXN*2];
map<int,int>mp;
bool cmp(cow_type xx,cow_type yy)
{
	return xx.p<yy.p;
}
void build(int num,int l,int r)
{
	t[num].l=l;
	t[num].r=r;
	t[num].f=false;
	if (l==r) return;
	int mid=(l+r)>>1;
	build(num*2,l,mid);
	build(num*2+1,mid+1,r);
}
int cover(int num,int l,int r)
{
	if (t[num].f) return 0;
	if (t[num].l>=l&&t[num].r<=r)
	{
		t[num].f=true;
		return 1;
	}
	if (t[num].l==t[num].r) return 0;
	int ret,mid=(t[num].l+t[num].r)>>1;
	if (r<=mid) ret=cover(num*2,l,r);
	else if (l>mid) ret=cover(num*2+1,l,r);
	else ret=cover(num<<1,l,r)|cover(num<<1|1,l,r);
	t[num].f=t[num].f|(t[num*2].f&t[num*2+1].f);
	return ret;
}
int main()
{
	f[0]=-1;
	scanf("%d",&n);
	F(i,1,n)
	{
		scanf("%d%d%d",&x,&a[i].p,&a[i].c);
		a[i].l=(-x-1)*a[i].c;
		a[i].r=-x*a[i].c;
		f[++cnt]=a[i].l;
		f[++cnt]=a[i].r;
	}
	sort(a+1,a+n+1,cmp);
	sort(f+1,f+cnt+1);
	F(i,1,cnt) if (f[i]!=f[i-1]) mp[f[i]]=++s;
	F(i,1,n)
	{
		a[i].l=mp[a[i].l];
		a[i].r=mp[a[i].r]-1;
	}
	build(1,1,s);
	F(i,1,n) ans+=cover(1,a[i].l,a[i].r);
	printf("%d\n",ans);
	return 0;
}