Khai bút đầu xuân

View as PDF
Submit solution
Points: 0.37 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
SPOJ
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Mùng ~1~ Tết, Nuga quyết định khai bút đầu xuân bằng cách giải một bài tập tin rất khó mà bạn ấy đã thấy trong một giấc mơ.

Cho một dãy số nguyên dương. Tính xem có bao nhiêu dãy con gồm các phần tử liên tiếp của nó mà có số lượng phần tử khác nhau nằm trong đoạn [~L~, ~U~].

Sau ~2~ tiếng ngồi cắn bút mà không giải xong, Nuga quyết định nhờ các bạn đội tuyển tin giúp đỡ. Nuga sẽ rất biết ơn nếu các bạn giải được bài tập này, và bạn ấy sẽ lì xì cho các bạn nhân dịp đầu năm mới.

Input

Dòng đầu tiên chứa các số nguyên dương ~N~, ~L~, ~U~. Sau đó là ~N~ dòng, mỗi dòng chứa một số nguyên dương ~X~ là một phần tử của dãy số.

Output

Một dòng duy nhất chứa một số nguyên thể hiện số dãy con có số lượng phần tử khác nhau nằm trong đoạn [~L~, ~U~].

Sample Input

4 1 2
231
19
7
19

Sample Output

8

Giới hạn

  • ~1 \le L \le U \le N \le 2^{20}~
  • ~1 \le X \le 2^{31} - 1~

Comments

Please read the guidelines before commenting.


  • -1
    luongxuantung50  commented on Nov. 27, 2024, 8:18 a.m.

    làm kiểu j v ak ai HD mình với


  • 1
    leduxhuy  commented on Nov. 25, 2024, 3:42 a.m.

    test đầu bài lấy

    [231],[19],[7],[19],[231,19],[19,7],[7,19],[19,7,19] (vì mỗi x là 1 phần tử)


  • -8
    anhtuanng04050405  commented on April 2, 2024, 2:55 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 19
    anhtri  commented on July 18, 2023, 4:34 p.m. ← edited

    My Solution:

    ĐPT: ~O(N * log_2N)~

    2 con trỏ + ý tưởng giống tính tổng đoạn [L, R] trong mảng cộng dồn.

    Gọi ~calc(x)~ là số lượng dãy con có số phần tử khác nhau không vượt quá ~x~ trong đoạn [1, N].

    Nếu chưa gặp dạng này bao giờ thì bạn có thể tham khảo qua phần Edu của Codeforces (nhớ Enroll phần pilot course trước nhé): link, phần Segment with Small Set nhé.

    ~res~ = ~calc(U) - calc(L - 1)~.

    code tham khảo: link.


  • -13
    trongtenlinhcbhk64  commented on July 4, 2023, 4:29 p.m. ← edit 4

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 1
    YukatouArimotou  commented on June 29, 2023, 1:31 p.m.

    có thể giải thích rõ hơn đề bài được không ạ :<


    • -8
      trongtenlinhcbhk64  commented on July 2, 2023, 4:28 p.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -18
    tboros2  commented on Nov. 26, 2022, 9:16 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.