fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. #include<complex>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6.  
  7. using namespace std;
  8.  
  9.  
  10. #define x() real()
  11. #define y() imag()
  12. #define endl '\n'
  13. #define ll long long
  14. typedef long double T;
  15. typedef complex<T> point;
  16. #define pii pair<int,int>
  17. #define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  18.  
  19.  
  20. using namespace __gnu_pbds;
  21. template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  22.  
  23. const int N = 2e5 + 5;
  24. int cnt[N], distinct, ar[N], nxt[N];
  25.  
  26. int main()
  27. {
  28. 	//fastIO;
  29.  
  30. 	int t = 1; //cin >> t;
  31.  
  32. 	while (t--)
  33. 	{
  34. 		int n, k; cin >> n >> k;
  35.  
  36. 		for (int i = 1	; i <= n; i++)cin >> ar[i];
  37.  
  38. 		nxt[n] = n + 1;
  39.  
  40. 		for (int i = n - 1; i >= 1; i--)
  41. 		{
  42. 			if (ar[i] == ar[i + 1])nxt[i] = nxt[i + 1];
  43. 			else nxt[i] = i + 1;
  44. 		}
  45.  
  46. 		int l = 1, r = 0;
  47. 		int ans = 0;
  48. 		int lim = 13;
  49.  
  50. 		while (1)
  51. 		{
  52. 			lim--;
  53.  
  54. 			if (distinct <= k && r < n)
  55. 			{
  56. 				r++;
  57. 				int val = ar[r];
  58.  
  59. 				cnt[val]++;
  60. 				if (cnt[val] == 1)distinct++;
  61.  
  62. 				if (distinct == k)
  63. 				{
  64. 					int len = nxt[l] - l;
  65. 					ans += len;
  66. 				}
  67. 			}
  68.  
  69. 			else
  70. 			{
  71. 				int val = ar[l];
  72. 				l++;
  73.  
  74. 				cnt[val]--;
  75. 				if (cnt[val] == 0)distinct--;
  76.  
  77. 				if (distinct == k)ans++;
  78. 			}
  79.  
  80. 			if (r == n && distinct < k)break;
  81. 		}
  82.  
  83. 		cout << ans << endl;
  84. 	}
  85.  
  86. 	return 0;
  87. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin 
5 2
1 2 1 2 3
stdout 
4
https://ideone.com/nnozVG
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

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!