Khai bút đầu xuân

Điểm: 0,37 (OI)

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

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

Input: stdin

Output: stdout

Nguồn bài:

SPOJ

Dạng bài

Ngôn ngữ cho phép

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

Sample Output

Giới hạn

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

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

hahuy0928 đã bình luận lúc 6, Tháng 2, 2025, 13:31

Mình chạy code thì vẫn ổn nhưng khi nộp bài thì test 2 bị value error nên cho mình hỏi là có trường hợp gì đặc biết không?

-3

luongxuantung50 đã bình luận lúc 27, Tháng 11, 2024, 8:18

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

1

leduxhuy đã bình luận lúc 25, Tháng 11, 2024, 3:42

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ử)

-9
anhtuanng04050405 đã bình luận lúc 2, Tháng 4, 2024, 2:55
include <bits/stdc++.h>

using namespace std;

int d(int n, int a[], int k){ unordered_map <int, int> dem; int cnt = 0; int ans = 0; int left = 0, r;

for (int r = 0; r < n; r++) { dem[a[r]]++; if (dem[a[r]] == 1) cnt++; while (cnt > k) { if (dem[a[left]] == 1) cnt--; dem[a[left]]--; left++; } ans += r - left + 1; } return ans;

}

int main() { iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0);

int n, l, u; cin >> n >> l >> u; int a[n]; for (int i = 0; i < n; i++) cin >> a[i]; cout << d(n, a, u) - d(n, a, l - 1); return 0;

}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

25

anhtri đã bình luận lúc 18, Tháng 7, 2023, 16:34 ← chỉnh sửa →

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.

-19

trongtenlinhcbhk64 đã bình luận lúc 4, Tháng 7, 2023, 16:29 ← sửa 4 →

em dùng set và hai con trỏ nhưng wa test 9 ai rảnh xem giúp em với ;)

https://ideone.com/FZtTak

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

0

YukatouArimotou đã bình luận lúc 29, Tháng 6, 2023, 13:31

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

-12

trongtenlinhcbhk64 đã bình luận lúc 2, Tháng 7, 2023, 16:28 ← chỉnh sửa →

đếm số đoạn con liên tiếp có số phần tử khác nhau ( tạm gọi là x ) thỏa mãn L <= x <= U thôi

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-20

tboros2 đã bình luận lúc 26, Tháng 11, 2022, 9:16

cho e xin tutorial :'(

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.