Problem Statement There are N buildings, Building 1, Building 2, …, Building N, arranged…
- User
Problem Statement There are N buildings, Building 1, Building 2, …, Building N, arranged in a line in this order. The height of Building i (1≤i≤N) is H i .
For each i=1,2,…,N, find the number of integers j (i<j≤N) satisfying the following condition:
There is no building taller than Building j between Buildings i and j. Constraints 1≤N≤2×10 5
1≤H i ≤N H i
=H j (i =j) All input values are integers. Input The input is given from Standard Input in the following format:
N H 1
H 2
… H N
Output For each i=1,2,…,N, let c i be the number of j satisfying the condition. Print c 1 ,c 2 ,…,c N in order, separated by spaces.
- Assistant
To solve the problem, we can compute the next greater element for each position, which is the next building taller than the current one. By finding the index of the next building taller than the current building, we can calculate the number of buildings that satisfy the condition for each position.
Here's the step-by-step solution:
-
Compute the Next Greater Element (NextGreater):
- We use a stack to find the next building with a greater height for each building.
- Initialize an empty stack.
- Iterate from the end of the building list to the beginning.
- For each building, if the stack is not empty and the current building is taller than the building at the top of the stack, we pop from the stack since the current building cannot be blocked by shorter buildings ahead.
- The next greater element for the current building is either the building at the top of the stack (if the stack is not empty) or a sentinel value (N+1) indicating there is no taller building ahead.
-
Calculate the Count for Each Building:
- The count of buildings satisfying the condition for each building is calculated as
NextGreater[i] - i - 1. - This calculation gives the number of buildings between the current building and the next taller building (or the end if there is no taller building).
- The count of buildings satisfying the condition for each building is calculated as
-
Output the Result:
- Print the counts for each building separated by spaces.
Below is the implementation of the above logic:
n_and_rest = input().split() N = int(n_and_rest[0]) if len(n_and_rest) > 1: H_list = list(map(int, n_and_rest[1:])) if len(H_list) < N: while len(H_list) < N: H_list.extend(map(int, input().split())) else: H_list = [] while len(H_list) < N: H_list.extend(map(int, input().split())) H = H_list[:N] N = len(H) NextGreater = [0]*N stack = [] for i in range(N-1,-1, -1): while stack and H[i] >= H[stack[-1]]: stack.pop() if stack: NextGreater[i] = stack[-1] else: NextGreater[i] = N stack.append(i) c = [NextGreater[i] - i -1 for i in range(N)] print(' '.join(map(str, c))) -
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.