fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = (1 << 20) + 5;  
  12.  
  13. int n, L, R;  
  14. int a[N]; 
  15.  
  16. void compress(int a[]) {
  17. 	vector<int> vals;  
  18. 	for (int i = 1; i <= n; i++) vals.push_back(a[i]);  
  19.  
  20. 	sort(vals.begin(), vals.end()); 
  21. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 
  22.  
  23. 	for (int i = 1; i <= n; i++) {
  24. 		a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1; 
  25. 	}
  26. }
  27.  
  28. int uniq_cnt = 0;  
  29. int cnt[N]; 
  30.  
  31. void add(int x) {
  32. 	cnt[x]++; 
  33. 	if (cnt[x] == 1) uniq_cnt++; 
  34. }
  35.  
  36. void remove(int x) {
  37. 	cnt[x]--; 
  38. 	if (cnt[x] == 0) uniq_cnt--; 
  39. }
  40.  
  41. ll solve(int X) {
  42. 	memset(cnt, 0, sizeof cnt); 
  43. 	uniq_cnt = 0;   
  44. 	ll ans = 0;  
  45. 	for (int r = 1, l = 1; r <= n; r++) {
  46. 		add(a[r]);  
  47. 		// l nhỏ nhất thoả mãn số phần tử phân biệt của đoạn [l, r] <= X
  48. 		while (l <= r && uniq_cnt > X) {
  49. 			remove(a[l]); 
  50. 			l++; 
  51. 		}
  52. 		ans += r - l + 1; 
  53. 	}
  54. 	return ans; 
  55. }
  56.  
  57. int main() {
  58. 	ios::sync_with_stdio(false); 
  59. 	cin.tie(nullptr); 	
  60. 	cin >> n >> L >> R;
  61. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  62.  
  63. 	compress(a);  
  64.  
  65. 	ll ans = solve(R) - solve(L - 1); 
  66.  
  67. 	cout << ans << '\n'; 
  68. }
Success #stdin #stdout 0.01s 9256KB
comments (?)
stdin
copy 
4 1 2
231
19
7
19
stdout
copy 
8
https://ideone.com/LHHHtj
language:
C++14 (gcc 8.3)
created:
346 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!