C++11(clang++ 3.9) 解法, 执行用时: 87ms, 内存消耗: 9336K, 提交时间: 2020-09-19 12:46:48

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int M=50010;
int n;
struct cow
{
	int L,R,h;
}a[M];
int f[M*2],s;
int ans;
map<int,int> m;
bool cmp(cow a,cow b)
{
	return a.h<b.h;
}
struct node
{
	int L,R;
	bool vis;
}t[M*8+5];
void build(int pos,int L,int R)
{
	t[pos].L=L;
	t[pos].R=R;
	t[pos].vis=0;
	if(L==R)
	return;
	int mid=(L+R)>>1;
	build(pos<<1,L,mid);
	build(pos<<1|1,mid+1,R);
}
int query(int pos,int ll,int rr)
{
	if(t[pos].vis)
	return 0;
	int L=t[pos].L;
	int R=t[pos].R;
	if(ll<=L&&rr>=R)
	{
		t[pos].vis=1;
		return 1;
	}
	if(L==R)
	return 0;
	int mid=(L+R)>>1,res=0;
	if(rr<=mid)
	res=query(pos<<1,ll,rr);
	else if(ll>mid)
	res=query(pos<<1|1,ll,rr);
	else
	res=query(pos<<1,ll,rr)|query(pos<<1|1,ll,rr);
	t[pos].vis=t[pos].vis|(t[pos<<1].vis&t[pos<<1|1].vis);
	return res;
}
int main()
{
	f[0]=-1;
	scanf("%d",&n);
	int x,y,c,cnt=0;
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		a[i].h=y;
		a[i].L=(-x-1)*c;
		a[i].R=(-x)*c;
		f[++cnt]=a[i].L;
		f[++cnt]=a[i].R;
	}
	sort(a+1,a+1+n,cmp);
	sort(f+1,f+1+cnt);
	for(int i=1;i<=cnt;++i)
	if(f[i]!=f[i-1])
	m[f[i]]=++s;
	for(int i=1;i<=n;++i)
	{
		a[i].L=m[a[i].L];
		a[i].R=m[a[i].R]-1;
	}
	build(1,1,s);
	for(int i=1;i<=n;++i)
	ans+=query(1,a[i].L,a[i].R);
	cout<<ans;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 53ms, 内存消耗: 9196K, 提交时间: 2020-09-23 21:22:51

#include<cstdio>
#include<algorithm>
using namespace std;
int sep[200005],tot,n,i,x,y,z,m,k,ans,flag,f[200005][20];
struct Node{
	int h,l,r;
}a[200005];
bool cmp(Node a,Node b)
{return a.h<b.h;}
void dfs(int l,int r,int l1,int r1,int k)
{
	if (l==l1&&r==r1)
	{	if (f[l][k]==0) flag=1,f[l][k]=1;
		return;}
	int mid=(l+r)>>1;
	if (f[l][k]) f[l][k-1]=1,f[mid+1][k-1]=1; 
	if (r1<=mid) dfs(l,mid,l1,r1,k-1);
	if (l1>mid)  dfs(mid+1,r,l1,r1,k-1);
	if (l1<=mid&&r1>mid) dfs(l,mid,l1,mid,k-1),dfs(mid+1,r,mid+1,r1,k-1);
	f[l][k]=f[l][k-1]&&f[mid+1][k-1];
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[i].h=y;a[i].l=-(x+1)*z;a[i].r=-x*z;
		sep[++tot]=a[i].l;sep[++tot]=a[i].r;
	}
	sort(sep+1,sep+tot+1);
	tot=unique(sep+1,sep+tot+1)-sep-1;
	for(i=1;i<=n;i++)
	{	a[i].l=lower_bound(sep+1,sep+tot+1,a[i].l)-sep;
		a[i].r=lower_bound(sep+1,sep+tot+1,a[i].r)-sep;}
	sort(a+1,a+n+1,cmp);
	ans=0;m=1;k=0;
	while(m<tot) m*=2,k++;
	for(i=1;i<=n;i++)
	{	flag=0;
		dfs(1,m,a[i].l,a[i].r-1,k);
		ans+=flag;}
	printf("%d\n",ans);
}