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

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
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 << " ";
    

    }