Dạ hội

Xem PDF

Đ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]\)\(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
6
Note
  • \(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


  • 18
    SPyofgame    8:00 p.m. 7 Tháng 6, 2020 đã chỉnh sửa

    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