fork download
  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
stdin
Standard input is empty
stdout
0