排队

NC220821. 排队

描述

有 $n$ 个小朋友排成一排，第 $i$ 个小朋友的位置是 $t[i]$ ，身高是 $h[i]$ ，视力为 $d[i]$ 。

小朋友 $i$ 能看到小朋友 $j$ ，需要满足2个条件

1. 小朋友 $j$ 在小朋友 $i$ 的视力范围内，用数学公式描述就是 $t[i]-d[i]<=t[j]<=t[i]+d[i]$

2. 这两个小朋友之间不存在高度不低于 $h_{j}$ 的小朋友

保证小朋友的位置各不相同

问题就是对于每一个小朋友，他能看到的小朋友个数是多少个？（不包括自己）

输入描述

第一行一个整数 。
接下来  行每行三个整数 。

输出描述

输出一行  个整数，表示每一个小朋友看的小朋友个数

示例1

输入:

输出:

1 2 2

说明:

1号小朋友只能看到2号小朋友，2号小朋友可以看到1和3号小朋友，3号小朋友可以看到2号小朋友和1号小朋友。

示例2

输入:

输出:

1 4 4 4 2

说明:

1号小朋友可以看到2号。2号小朋友可以看到1、3、4、5号。3号小朋友可以看到1、2、4、5号。4号小朋友可以看到1、2、3、5号。5号小朋友可以看到2、4号。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 402ms, 内存消耗: 7172K, 提交时间: 2021-05-09 22:26:45

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 300010;

int stk[N],ans[N],n;
struct node{
	int t,h,d,id;
}p[N];

bool cmp1(node a,node b)
{
	return a.t < b.t;
}

bool cmp2(node a,node b)
{
	return a.t > b.t;
}

void mostk()
{
	int top = 0;
	for(int i = 0;i < n;i++)
	{
		if(i)
		{
			int l = 1,r = top;
			while(l < r)
			{
				int mid = (l+r)/2;
				if(abs(p[i].t-p[stk[mid]].t) > p[i].d)
					l = mid+1;
				else
					r = mid;
			}
			ans[p[i].id] += top-l+1;
		}
		while(top && p[stk[top]].h <= p[i].h)
			top--;
		stk[++top] = i;
	}
}

int main()
{
	cin >> n;
	for(int i = 0;i < n;i++)
	{
		cin >> p[i].t >> p[i].h >> p[i].d;
		p[i].id = i;
	}
	sort(p,p+n,cmp1);
	mostk();
	sort(p,p+n,cmp2);
	mostk();
	for(int i = 0;i < n;i++)
		cout << ans[i] << " ";
	
	return 0;
}