Buổi hòa nhạc - LCOJ: Luyện Code Online Judge

CONCERT - Buổi hòa nhạc

Điểm: 1,00 (OI)

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

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

Tác giả:

Hiếu Nguyễn

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

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

Please read the guidelines before commenting.

include <bits/stdc++.h>

using namespace std;

int main(){ ios::syncwithstdio(false); cin.tie(nullptr);

int N;
cin >> N;
vector&lt;long long> h(N);
for(int i = 0; i < N; i++){
    cin >> h[i];
}

stack&lt;pair&lt;long long,long long>> st;  
// mỗi phần tử: (height, count_same_height)
long long ans = 0;

for(int i = 0; i < N; i++){
    long long cur = h[i];
    long long cnt = 1;

    // pop mọi người có height < cur
    while(!st.empty() && st.top().first < cur){
        ans += st.top().second;
        st.pop();
    }

    // nếu top có cùng height
    if(!st.empty() && st.top().first == cur) {
        // với tất cả người cùng height: mỗi người đó + người hiện tại
        ans += st.top().second;
        cnt = st.top().second + 1;
        st.pop();

        // nếu sau khi pop còn người cao hơn phía sau → người hiện tại vẫn nhìn thấy 1
        if(!st.empty()) ans += 1;
    }
    else {
        // nếu stack không rỗng (top cao hơn hiện tại), họ nhìn thấy nhau
        if(!st.empty()) ans += 1;
    }

    st.push({cur, cnt});
}

cout << ans << "\n";
return 0;

}

0

kieuquocminh đã bình luận lúc 31, Tháng 10, 2025, 13:17

csvsv

0
khoihahaha đã bình luận lúc 9, Tháng 6, 2025, 14:30
Ý tưởng: dùng stack(st) và hash map(cnt) để đếm

Khi gặp thằng h > st.top() => giảm số lượng của st.top() trong hash map, pop nó, tăng giá trị biến ans lên 1(chỉ kề nhau mới thấy, trước đó nữa thì không)

Loại trường hợp lớn hơn rồi còn trường hợp bé hơn hoặc bằng

Khi gặp h == st.top() => cộng ans cho số lần xuất hiện của st.top() trong stack (do cao bằng thì thấy nhau hết). Do có thể có thằng trước đó thấp hoặc cao hơn(st.size() > cnt[h]) -> cộng thêm một

Khi h != st.top() tức h < st.top() -> cộng ans thêm 1 kề nhau.

Code đã AC:

int n; std::cin >> n; std::unordered_map<int, int> cnt; std::stack<int> st; long long ans = 0; for (int i = 0; i < n; i++) { std::cin >> arr[i]; while (!st.empty() && arr[i] > st.top()) { cnt[st.top()]--; st.pop(); ans++; } if (!st.empty()) ans += st.top() == arr[i] ? cnt[arr[i]] + int(st.size() > cnt[arr[i]]) : 1; st.push(arr[i]); cnt[arr[i]]++; } std::cout << ans;

Độ phức tạp thời gian: O(n)

0

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

Moi nguoi goi y cach lam duoc khong plz. Dung cho 1 upvote + 0.5 robux

1

0988440189 đã bình luận lúc 20, Tháng 5, 2025, 7:17

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 ...