记录编号	387520	评测结果	AAAAAAAAAAAAAAA
题目名称	奔跑	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.251 s
提交时间	2017-03-26 20:24:06	内存使用	1.78 MiB

#include<cstdio>
#include<queue>
#include<algorithm>
#define MAXN 50010
#define INF 0x7fffffff
using namespace std;
namespace IO{
	char buf[1<<15],*fs,*ft;
	inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int qr(){
		int x=0,rev=0,ch=gc();
		while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=gc();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
		return rev?-x:x;}
}using namespace IO;
/********************************************************************************************************/
struct Event{
	bool type;
	int pos,num;
}a[MAXN<<1];
struct Cow{
	int x,y,t,l,r;
}c[MAXN];
bool operator < (Event x,Event y){
	if(x.pos!=y.pos)return x.pos<y.pos;
	if(x.type!=y.type)return x.type;
	return x.num>y.num;}
bool cmp(Cow x,Cow y){return x.y>y.y;}
int N,ans=0,r[MAXN];
bool vis[MAXN]={0};
priority_queue<int>q;
int sb(){
	freopen("stampede.in","r",stdin);
	freopen("stampede.out","w",stdout);
	N=qr();r[0]=INF;q.push(0);
	for(int i=1;i<=N;i++){
		c[i].x=qr();c[i].y=qr();c[i].t=qr();
		c[i].l=(-c[i].x-1)*c[i].t;
		c[i].r=c[i].l+c[i].t;}
	sort(c+1,c+1+N,cmp);
	for(int i=1;i<=N;i++){
		a[i].pos=c[i].l;r[i]=c[i].r;
		a[i+N].pos=r[i];
		a[i].num=a[i+N].num=i;
		a[i].type=1;a[i+N].type=0;}
	N<<=1;
	sort(a+1,a+N+1);
	for(int i=1;i<=N;i++){
		if(a[i].type)q.push(a[i].num);
		else while(q.top()&&r[q.top()]<=a[i].pos){q.pop();}
		vis[q.top()]=1;}
	N>>=1;
	for(int i=1;i<=N;i++){if(vis[i])ans++;}
	printf("%d",ans);
	return 0;}
int chh=sb();
int main(){;}