Phân tích và ý tưởng

Ta cần xét các trận theo đúng thứ tự diễn ra, vì một kỷ lục chỉ được tính khi điểm của trận hiện tại vượt qua kỷ lục đã có trước trận đó.

Dùng hai biến:

• mn: điểm thấp nhất đã ghi nhận, ban đầu bằng ~x~.
• mx: điểm cao nhất đã ghi nhận, ban đầu bằng ~x~.

Dùng a để đếm số lần phá kỷ lục thấp nhất và b để đếm số lần phá kỷ lục cao nhất.

Với mỗi điểm ~v~:

• Nếu ~v < mn~: tăng a lên 1, cập nhật mn = v.
• Nếu ~v > mx~: tăng b lên 1, cập nhật mx = v.
• Nếu ~mn \le v \le mx~: không có kỷ lục mới. Điểm bằng kỷ lục cũ không được tính.

Lưu ý về thứ tự nhập: Theo đề, ~x~ nằm ở dòng cuối, sau dãy ~n~ điểm. Vì vậy có thể lưu dãy vào mảng rồi mới đọc ~x~ và xử lý.

Các bước thực hiện

1. Nhập ~n~ và dãy ~n~ điểm vào mảng.
2. Nhập điểm ban đầu ~x~.
3. Gán mn = mx = x, a = b = 0.
4. Duyệt dãy từ trái sang phải; cập nhật kỷ lục và bộ đếm tương ứng.
5. In a và b, cách nhau một dấu cách.

Minh họa ví dụ

Kỷ lục ban đầu: thấp nhất = 100, cao nhất = 100.

Kết quả: 4 2.

Độ phức tạp

• Thời gian: ~O(n)~ vì chỉ duyệt dãy một lần.
• Bộ nhớ: ~O(n)~ để lưu dãy trước khi đọc ~x~.

Code mẫu C++17

#include <bits/stdc++.h>
using namespace std;

int n, x, mn, mx, a, b;
int s[100005];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    cin >> x;

    mn = mx = x;
    a = b = 0;

    for (int i = 1; i <= n; i++)
    {
        if (s[i] < mn)
        {
            a++;
            mn = s[i];
        }
        if (s[i] > mx)
        {
            b++;
            mx = s[i];
        }
    }

    cout << a << " " << b << endl;
    return 0;
}

Lưu ý khi làm bài

• Không sắp xếp dãy: thứ tự các trận quyết định thời điểm phá kỷ lục.
• So sánh nghiêm ngặt bằng < và >, không dùng <= hoặc >=.
• Trận đầu tiên có điểm ~x~ chỉ dùng để khởi tạo, không tính là lần phá kỷ lục.
• Khi mọi trận thêm đều có điểm bằng ~x~, kết quả là 0 0.