P3114 [USACO15JAN]踩踏Stampede

我一开始看错题了，看成每秒走\(c_i\)个单位了，于是样例答案就变成了3。。害我调好久，还以为样例错了

对于每头奶牛，我们求出它经过\(y\)轴的时间段，然后离散化一下，将奶牛按照从低到高的顺序排序，区间上记录最新经过的奶牛，如果当前奶牛的区间都已经被覆盖过了，那么说明完全被遮挡，反之则可以被看到，这样的话由于已经排过序了，可以很容易看出这是正确的，用线段树实现即可

线段树我是这么实现的，初始值为无限大，\(update\)时直接覆盖修改的区间，这样查询区间最大值，只要不是无限大，就说明完全被遮挡

下面放代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#define ll long long

#define gc getchar

#define maxn 50005

using namespace std;

inline ll read(){

	ll a=0;int f=0;char p=gc();

	while(!isdigit(p)){f|=p=='-';p=gc();}

	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

	return f?-a:a;

}int n,ans,cnt,x[maxn],c[maxn];ll b[maxn<<1];

struct ahaha{

	int h,l,r;

	inline bool friend operator<(const ahaha x,const ahaha y){

		return x.h<y.h;

	}

}q[maxn];

struct ahaha1{

	int v,lz;

	ahaha1(){

		v=1000001;

		lz=-1;

	}

}t[maxn<<3];

#define lc p<<1

#define rc p<<1|1

inline void pushup(int p){

	t[p].v=max(t[lc].v,t[rc].v);

}

inline void pushdown(int p){

	int &lz=t[p].lz;

	t[lc].v=lz;t[lc].lz=lz;

	t[rc].v=lz;t[rc].lz=lz;

	lz=-1;

}

void update(int p,int l,int r,int L,int R,int z){

	if(l>R||r<L)return;

	if(L<=l&&r<=R){t[p].v=z;t[p].lz=z;return;}

	int m=l+r>>1;if(~t[p].lz)pushdown(p);

	update(lc,l,m,L,R,z);update(rc,m+1,r,L,R,z);

	pushup(p);

}

int query(int p,int l,int r,int L,int R){

	if(l>R||r<L)return -1;

	if(L<=l&&r<=R)return t[p].v;

	int m=l+r>>1;if(~t[p].lz)pushdown(p);

	return max(query(lc,l,m,L,R),query(rc,m+1,r,L,R));

}

int main(){

	n=read();

	for(int i=1;i<=n;++i){

		x[i]=read();q[i].h=read();c[i]=read();

		b[++cnt]=1ll*-x[i]*c[i];

		b[++cnt]=1ll*(-x[i]-1)*c[i];

	}

	sort(b+1,b+cnt+1);cnt=unique(b+1,b+cnt+1)-b-1;

	for(int i=1;i<=n;++i){

		q[i].l=lower_bound(b+1,b+cnt+1,1ll*(-x[i]-1)*c[i])-b;

		q[i].r=lower_bound(b+1,b+cnt+1,1ll*-x[i]*c[i])-b;

	}

	sort(q+1,q+n+1);

	for(int i=1;i<=n;++i){

		int v=query(1,1,cnt,q[i].l,q[i].r-1);

		if(v==1000001)++ans;

		update(1,1,cnt,q[i].l,q[i].r-1,q[i].h);

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

P3114 [USACO15JAN]踩踏Stampede

最新文章

热门文章