Dạ hội

Tác giả:

cuom1999

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Dạ hội cuối năm (prom) là một sự kiện trọng đại trước khi kết thúc năm học ở trường THPT chuyên Lê Quý Đôn. Vì đã là năm cuối cấp nên Minh Huy quyết tâm mời cho bằng được chị Constant tham gia khiêu vũ cùng mình. Tiếc thay, chị Constant đã nhận lời mời làm bạn nhảy của chuyên gia tin học Flow God (dưới tư cách cựu học sinh) nên đành phải từ chối Minh Huy. Không bỏ cuộc, Minh Huy liên tục đưa ra những hứa hẹn đầy hấp dẫn để lôi kéo khiến chị Constant phải đôi chút xiêu lòng: Chị Constant đồng ý hủy hẹn với Flow God để đi với Minh Huy nếu như cậu có thể tính được số lượng dãy con có độ cồng kềnh nhỏ nhất trong một dãy số.

Với một dãy số nguyên dương gồm \(n\) số \(a_1,a_2,\cdots,a_n\), độ cồng kềnh của một dãy con liên tiếp \(a_i,a_{i+1},\cdots,a_j\) là hiệu của số lớn nhất trong dãy và số nhỏ nhất trong dãy. Ví dụ: độ cồng kềnh của \([1,3,2]\) là \(3−1=2\).

Chị Constant muốn tìm dãy con liên tiếp có độ cồng kềnh nhỏ nhất có thể, và tổng quát hơn, đếm xem có bao nhiêu dãy con liên tiếp có độ cồng kềnh nhỏ nhất như thế. Bạn hãy giúp Minh Huy giải đáp lời thách đố này để được dự prom cùng chị Constant nhé!

Input

Dòng đầu tiên chứa một số nguyên dương \(n\)
Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,\cdots,a_n (1 \leq a_i \leq n)\)

Output

In ra một số nguyên dương, là số lượng dãy con liên tiếp có độ cồng kềnh nhỏ nhất.

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(n \leq 300\).
Subtask \(2\) (\(30\%\) số điểm): \(n \leq 3,000\).
Subtask \(3\) (\(40\%\) số điểm): \(n \leq 300,000\).

Example

Test 1

Input

3
1 1 1

Output

Note

Có \(6\) dãy con có độ cồng kềnh bằng \(0\):\([a_1],[a_2],[a_3],[a_1,a_2],[a_2,a_3],[a_1,a_2,a_3]\)

Bình luận

`Spoiler Alert`

Hint 1

Dãy có độ cồng kềnh nhỏ nhất là dãy có 1 phần tử

Hint 2

Cần đếm số dãy có độ cồng kềnh là 0

Hint 3

Cần đếm số dãy mà các phần tử là bằng nhau

Hint 4

Với mỗi dãy bằng nhau có độ dài \(n\) sẽ có \(\frac{n * (n + 1)}{2}\) cách chọn

Reference AC code | \(O(n)\) time | \(O(1)\) auxiliary space | Online Solving

C++

ll f(int x) { return 1LL * x * (x + 1) / 2; }
int main()
{
    int n = readInt();

    ll res = 0;
    int cnt = 0;
    for (int pre = 0, cur; n--; pre = cur)
    {
        cin >> cur;
        if (cur == pre) cnt++;
        else
        {
            res += f(cnt);
            cnt = 1;
        }
    }
    res += f(cnt);

    cout << res;
    return 0;
}

0
lagiahuy 6:52 p.m. 15 Tháng 10, 2021 ← chỉnh sửa 2 →
1LL là gì thế bạn!?

ll f(int x) { return 1LL * x * (x + 1) / 2; }

0

SPyofgame 10:42 p.m. 15 Tháng 10, 2021

ý mình sài hint 3 cho hint 4 ý

0

lagiahuy 10:34 a.m. 16 Tháng 10, 2021

ok bạn, đã hiểu.

1 bình luận nữa