fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<ll> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22.  
  23. int a[500001];
  24. int L[500001];
  25. const int MOD = 1e9 + 7;
  26.  
  27. ll mult(ll a, ll b)
  28. {
  29. 	ll ans = (a*b)%MOD;
  30. 	if(ans<0) ans+=MOD;
  31. 	return ans;
  32. }
  33.  
  34. ll add(ll a, ll b)
  35. {
  36. 	a+=b;
  37. 	while(a>=MOD) a-=MOD;
  38. 	while(a<0) a+=MOD;
  39. 	return a;
  40. }
  41.  
  42. ll dp[500001];
  43. const int INF = int(1e7);
  44. int cnt[500005];
  45. int run;
  46. int n,k; 
  47.  
  48. void add(int x)
  49. {
  50. 	if(cnt[x]==0&&x<=k)
  51. 	{
  52. 		run++;
  53. 	}
  54. 	cnt[x]++;
  55. }
  56.  
  57. void del(int x)
  58. {
  59. 	if(cnt[x]==1&&x<=k)
  60. 	{
  61. 		run--;
  62. 	}
  63. 	cnt[x]--;
  64. }
  65.  
  66. ll sum[500001];
  67.  
  68. ll S(int l, int r)
  69. {
  70. 	if(l>r) return 0;
  71. 	if(l<0) return add(sum[r],1);
  72. 	else if(l==0) return sum[r];
  73. 	else return add(sum[r],MOD-sum[l-1]);
  74. }
  75.  
  76. int main()
  77. {
  78. 	ios_base::sync_with_stdio(0); cin.tie(0);
  79. 	cin>>n>>k;
  80. 	for(int i=0;i<n;i++)
  81. 	{
  82. 		cin>>a[i];
  83. 		a[i]=min(a[i],500001);
  84. 	}
  85. 	L[0]=0;
  86. 	if(k==0&&a[0]==0) L[0]=INF;
  87. 	int ptr=0;
  88. 	run=0;
  89. 	if(L[0]==0)
  90. 	{
  91. 		add(a[0]);
  92. 	}
  93. 	else
  94. 	{
  95. 		ptr=1;
  96. 	}
  97. 	for(int i=1;i<n;i++)
  98. 	{
  99. 		add(a[i]);
  100. 		while(run>=k+1&&ptr<i)
  101. 		{
  102. 			del(a[ptr]);
  103. 			ptr++;
  104. 		}
  105. 		if(ptr==i&&run>=k+1)
  106. 		{
  107. 			del(a[i]);
  108. 			ptr=i+1;
  109. 			L[i]=INF;
  110. 		}
  111. 		else
  112. 		{
  113. 			L[i]=ptr;
  114. 		}
  115. 	}
  116. 	if(L[0]==0) dp[0]=1;
  117. 	else dp[0]=0;
  118. 	sum[0]=dp[0];
  119. 	for(int i=1;i<n;i++)
  120. 	{
  121. 		dp[i]=S(L[i]-1,i-1);
  122. 		sum[i]=add(sum[i-1],dp[i]);
  123. 	}
  124. 	cout<<dp[n-1]<<'\n';
  125. }
  126.  
Success #stdin #stdout 0s 29736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/UNyNVe
language:
C++14 (gcc 8.3)
created:
6 years 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!