Độ dốc của mảng - LCOJ: Luyen Code Online

PTIT032 - Độ dốc của mảng

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho 1 dãy số có ~n~ phần tử, độ dốc của phần tử thứ ~i~ là ~i_{cost}~ được tính như sau:

~L~ là phần tử xa nhất phía bên trái ~i~ sao cho giá trị từ ~i~ đến ~L~ giảm dần.
~R~ là phần tử xa nhất phía bên phải ~i~ sao cho giá trị từ ~i~ đến ~R~ giảm dần.
~i_{cost}~ là số phần tử từ ~L~ đến ~R~.
Lưu ý: "giảm dần" (không chấp nhận bằng nhau), khác với "không tăng"

Nhiệm vụ của bạn là tính ~i_{cost}~ của cả ~n~ phần tử.

Input

Dòng đầu tiên gồm 1 số nguyên ~n~ (~1 \le n \le 2 \cdot 10^5~) là số lượng phần tử.
Dòng tiếp theo gồm ~n~ số nguyên ~A_1, A_2, …, A_N~ (~1 \le A_i \le 10^6~).

Output

In ra ~n~ số trên 1 hàng, cách nhau bởi 1 dấu cách là kết quả của bài toán.

Sample

Input #1

7
1 2 3 4 3 3 1

Output #1

1 2 3 5 1 2 1

Problem source: CLB Lập Trình PTIT

Bình luận

Hãy đọc nội quy trước khi bình luận.

-1

dongluong123 đã bình luận lúc 14, Tháng 5, 2025, 1:07

include <bits/stdc++.h>

using namespace std;

int main(){ int n; cin >> n; vector<int> a(n);

for(int i = 0; i < n; i++){
    cin >> a[i];
}

vector<int> b; 

for(int i = 0; i < n; i++){
    int cnt_l = 0, cnt_r = 0;

    int l = i - 1;
    while(l >= 0 && a[l] < a[l+1]){ // giảm dần nghiêm ngặt bên trái
        cnt_l++;
        l--;
    }

    int r = i + 1;
    while(r < n && a[r-1] > a[r]){ // giảm dần nghiêm ngặt bên phải
        cnt_r++;
        r++;
    }

    b.push_back(cnt_l + cnt_r + 1); // +1 vì tính cả chính nó
}

for(int x : b) cout << x << " ";

}