Elearning CodePath – CTP Online Judge

Cổ phiếu

2425_NGHEAN_TS10

🟢 Easy

Theo dõi giá cổ phiếu trong n ngày, ngày i có giá trị ai (`ai ≤ 10^5`). Ngày i được gọi là tăng trưởng nếu tồn tại ngày j trước đó (`j<i`) có `aj<ai`. Với mỗi i, chọn j xa nhất về phía trước (tức chỉ số nhỏ nhất) thỏa `aj<ai`. Độ tăng trưởng của ngày `i` là số ngày từ `j` đến ngay trước `i`, tức `i-j`. Nếu không tồn tại j thì độ tăng trưởng bằng 0.

Yêu cầu: Tính độ tăng trưởng của từng ngày.

## Dữ liệu vào:
- Dòng 1: số nguyên dương n.
- Dòng 2: n số nguyên dương a1,...,an (ai≤10^5).

## Kết quả: 
In n số là độ tăng trưởng tương ứng.

## Ví dụ 1
`Input`
6
10 8 5 3 9 45
`Output`
0 0 0 0 3 5
Giải thích: Với ngày 5, giá 9, ngày xa nhất về bên trái có giá nhỏ hơn là ngày 2 (giá 8), nên độ tăng trưởng là `5-2=3`. Với ngày 6, ngày 1 có giá `10<45` nên độ tăng trưởng là `6-1=5`.

## Ví dụ 2
`Input`
7
16 4 6 3 2 18 15 
`Output`
0 0 1 0 0 5 5
Giải thích: Ngày 3 có giá 6, ngày 2 (giá 4) là ngày xa nhất trước đó có giá nhỏ hơn nên kết quả 1. Ngày 6 (18) và ngày 7 (15) đều có thể dùng ngày 1 (`16<18` chỉ đúng với ngày 6; với ngày 7, ngày 1 không nhỏ hơn 15, nên ngày xa nhất phù hợp là ngày 2, khoảng cách 5).

## Subtasks:
- `30%: 0<n≤5×10^5.`
- `70%: 5×10^5<n<5×10^6.`

✅ Đã AC: 0 / 6 submissions