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
The problem requires you to find for each building (i), the number of buildings (j) that satisfy the condition: there is no building taller than Building (j) between buildings (i) and (j).
To solve this efficiently, we can use the concept of "Next Greater Element" (NGE). For each building (i), NGE is the smallest index (j > i) such that (H_j > H_i).
Here's the step-by-step solution:
- Initialize an array
next_greaterof size (N+1) and a stackS. - Iterate from the end of the
Harray to the start (from (i = N) down to (1)).- While the stack is not empty and (H[S.top()] \leq H[i]), pop the stack.
- If the stack is empty after popping, set
next_greater[i] = N + 1. - If the stack is not empty, set
next_greater[i] = S.top(). - Push the current index (i) onto the stack.
- For each building (i), calculate (c_i = \text{next_greater}[i] - i - 1).
This method ensures that for each building (i), you efficiently compute the number of buildings (j > i) until a building taller than (H_i) is encountered. Since the heights are unique (as per the problem constraints), this tall building effectively "blocks" the sequence, and thus any building beyond it cannot be counted for building (i).
Here's the code based on this method:
N,*rest=map(int,open(0).read().split()) H=rest[:N] next_greater = [0]*(N+1) c = [0]*N stack = [] for i in range(N-1, -1, -1): while stack and H[stack[-1]] <= H[i]: stack.pop() if not stack: next_greater[i] = N else: next_greater[i] = stack[-1] c[i] = next_greater[i] - i -1 stack.append(i) print(' '.join(map(str, c))) - Initialize an array
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.