CONCERT - Buổi hòa nhạc
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
Có ~N~ người đang xếp hàng chờ đợi để vào một buổi hòa nhạc. Mọi người cảm thấy buồn chán khi chờ đợi nên họ tìm những người thân của họ trong hàng đang xếp. Hai người ~A~ và ~B~ có thể nhìn thấy nhau nếu họ đang đứng ngay cạnh nhau hoặc không có người nào cao hơn ~A~ hoặc ~B~ đứng giữa. Hãy xác định số cặp có thể nhìn thấy nhau.
Input
- Dòng đầu chứa số nguyên dương ~N~ là số người đang đứng xếp hàng.
- Dòng thứ hai chứa ~N~ số nguyên dương ~h_1, h_2, …, h_N~ theo thứ tự là độ cao của những người đang đứng trong hàng.
Giới hạn:
- ~1 ≤ n ≤ 10^5; 1 ≤ h_i ≤ 10^9~.
Output
- Một số nguyên duy nhất là số cặp có thể nhìn thất nhau.
Sample
Input #1
7
2 4 1 2 2 5 1
Output #1
10
Hint
- Xét #1, ~10~ cặp có thể nhìn thấy nhau là ~(A, B), (B, C), (B, D), (B, E), (C, D), (B, F), (D, F), (D, E), (E, F), (F, G)~ như hình vẽ:
Problem source: Chuyên Sơn La Online Judge
Bình luận
Moi nguoi goi y cach lam duoc khong plz. Dung cho 1 upvote + 0.5 robux
tìm vị trí của thằng cao hơn gần nhất đứng bên phải của thằng đang xét ( lấy vị trí trừ đi vị trí thằng đang xét ) là ra của từng thanngwf rồi duyệt cả mảng là ra tổng cần tìm á bạn ...