fork(1) download 
  1. #include <bits/stdc++.h>
  2. #define pii pair < int , int >
  3. #define ll long long
  4. #define pipii pair < int , pair < int , int > >
  5. #define mp make_pair
  6. #define pb push_back
  7. #define fi first
  8. #define se second
  9. #define pri_que priority_queue 
  10. using namespace std;
  11. const int maxn=3e5+14;
  12. int n , k;
  13. int a[maxn];
  14. void sub12(){
  15. 	if (k >= n - 1 ) {
  16. 		cout << n;
  17. 		return;
  18. 	}
  19. 	int ans = k + 1;
  20. 	int cnt = 0;
  21. 	for (int i = 1; i <= n; i++, cnt ++){
  22. 		unordered_map < int , int > m;
  23. 		int maxtanso = 1;
  24.  
  25. 		for (int j = i; j <= n; j ++, cnt++){
  26. 			m[a[j]]++;
  27. 			maxtanso = max(maxtanso, m[a[j]]);
  28. 			if ( j - i + 1 - maxtanso > k) break;
  29. 			ans = max(ans, j - i + 1);
  30. 		}
  31. 	}
  32. 	cout << ans << endl ;
  33. }
  34.  
  35. void sub3(){
  36. 	unordered_map < int , vector < pii > > m ;
  37. 	unordered_map < int , int > cnt ;
  38.  
  39. 	for (int i = 1; i <= n; i++){
  40. 		if (cnt[a[i]] == 0){
  41. 			m[a[i]].pb(mp(0, 0));
  42. 		}
  43. 		cnt[a[i]] ++;
  44. 		m[a[i]].pb(mp(i, cnt[a[i]]));
  45. 	}
  46.  
  47. 	int ans = k + 1;
  48.  
  49. 	if (k >= n - 1 ) {
  50. 		cout << n;
  51. 		return ;
  52. 	}
  53.  
  54. 	unordered_map < int , int > dem ;
  55. 	for (int i = 1; i <= n; i++){
  56. 		dem[a[i]] ++;
  57. 		int l = 1, r = m[a[i]].size();
  58. 		int res = 1;
  59. 		while (l <= r) {
  60. 			int d = (l + r) >> 1;
  61. 			if (m[a[i]][d].fi >= i) {
  62. 				r = d - 1;
  63. 				continue;
  64. 	    	}
  65. 	    	int maxtanso = dem[a[i]] - m[a[i]][d].se + 1;
  66. 			if (i + 1 - maxtanso - k > m[a[i]][d].fi) l = d + 1;
  67. 			else {
  68. 				res = max(res, min(maxtanso + k , n));
  69. 				r = d - 1;
  70. 			}
  71.  
  72. 		}
  73. 		ans = max(ans , res);
  74. 	}
  75.  
  76. 	cout << ans ;
  77. }
  78. int main(){
  79. 	ios_base::sync_with_stdio(0);
  80. 	cin.tie(0);    cout.tie(0);
  81. 	if (fopen("SEQ.INP","r")){
  82. 		freopen("SEQ.INP","r",stdin);
  83. 		freopen("SEQ.OUT","w",stdout);
  84. 	}
  85. 	cin >> n >> k;
  86. 	for (int i = 1; i <= n; i++){
  87. 		cin >> a[i];
  88. 	}
  89.     if (n <= 5000) sub12();
  90.     else sub3();
  91. 	return 0;
  92. }
  93.  
  94.  
Success #stdin #stdout 0s 5276KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/HBIPdo
language:
C++14 (gcc 8.3)
created:
2 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!