fork download
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug cout << "ok\n";
  4. #define SQR(x) (1LL * ((x) * (x)))
  5. #define MASK(i) (1LL << (i))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10.  
  11. #define mp make_pair
  12. #define pii pair<int, int>
  13. #define pll pair<ll, ll>
  14. #define pli pair<ll, int>
  15. #define vi vector<int>
  16. #define vll vector<ll>
  17.  
  18. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef unsigned int ui;
  24.  
  25. using namespace std;
  26.  
  27. const int M = 1e9 + 7;
  28. const int INF = 1e9 + 7;
  29. const ll INFLL = (ll)2e18 + 7LL;
  30. const ld PI = acos(-1);
  31.  
  32. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  33. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  34.  
  35. template<class _, class __>
  36. bool minimize(_ &x, const __ y){
  37. if(x > y){
  38. x = y;
  39. return true;
  40. } else return false;
  41. }
  42. template<class _, class __>
  43. bool maximize(_ &x, const __ y){
  44. if(x < y){
  45. x = y;
  46. return true;
  47. } else return false;
  48. }
  49.  
  50. //--------------------------------------------------------------
  51.  
  52. const int MaxN = 2e5+7;
  53.  
  54. int n,u,v,a[MaxN];
  55.  
  56. //namespace sub1 {
  57. // bool check() {
  58. // return n <= 5000;
  59. // }
  60. //
  61. // int f[5007][5007];
  62. // int lab[5007];
  63. //
  64. // int GR(int u) {
  65. // return lab[u] < 0 ? u : lab[u] = GR(lab[u]);
  66. // }
  67. //
  68. // void sol() {
  69. // for (int i=1;i<=n;i++) {
  70. // int p = 0;
  71. // for (int j=0;j<=n;j++) {
  72. // lab[j] = -1;
  73. // }
  74. // for (int j=i;j<=n;j++) {
  75. // lab[a[j]] = a[j] + 1;
  76. // p = GR(p);
  77. // f[p][j - i + 1]++;
  78. // }
  79. // }
  80. // for (int i=1;i<=n;i++) {
  81. // int res = 0;
  82. // for (int j=u;j<=min(n,v);j++) {
  83. // res += f[j][i];
  84. // }
  85. // cout << res << ' ';
  86. // }
  87. // }
  88. //}
  89.  
  90. namespace sub2 {
  91. bool check() {
  92. return true;
  93. }
  94.  
  95. int cnt[MaxN],f[MaxN];
  96. int res[MaxN];
  97.  
  98. void calc(int u,int val) {
  99. // cout << u << ' ' << val << '\n';
  100. memset(cnt,0,sizeof(cnt));
  101. memset(f,0,sizeof(f));
  102. int cntt = 0;
  103. int cur = 0;
  104. while (cur < n && cntt < u) {
  105. cur++;
  106. cnt[a[cur]]++;
  107. if (a[cur] < u && cnt[a[cur]] == 1) cntt++;
  108. }
  109. if (cntt < u) return;
  110. cnt[a[cur]]--;
  111. int curr = 1;
  112. for (int i=cur;i<=n;i++) {
  113. cnt[a[i]]++;
  114. while (curr < i && (a[curr] >= u || cnt[a[curr]] > 1)) {
  115. cnt[a[curr]]--;
  116. curr++;
  117. }
  118. // cout << i << ' ' << curr << '\n';
  119. f[i - curr + 1]++;
  120. f[i+1]--;
  121. }
  122. // for (int i=1;i<=n;i++) cout << f[i] << ' '; cout << '\n';
  123. for (int i=1;i<=n;i++) {
  124. f[i] += f[i-1];
  125. }
  126. for (int i=1;i<=n;i++) {
  127. res[i] += f[i]*val;
  128. }
  129. }
  130.  
  131. void sol() {
  132. // for (int i=1;i<=n;i++) {
  133. // res[i] = n - i + 1;
  134. // }
  135. calc(u,1);
  136. // for (int i=1;i<=n;i++) cout << res[i] << ' '; cout << '\n';
  137. calc(v+1,-1);
  138. for (int i=1;i<=n;i++) cout << res[i] << ' ';
  139. }
  140. }
  141.  
  142. void sol() {
  143. cin >> n >> u >> v;
  144. for (int i=1;i<=n;i++) cin >> a[i];
  145. // if (sub1::check()) {
  146. // sub1::sol();
  147. // return;
  148. // }
  149. if (sub2::check()) {
  150. sub2::sol();
  151. return;
  152. }
  153. }
  154.  
  155. int main() {
  156. freopen("EAT.inp","r",stdin);
  157. freopen("EAT.out","w",stdout);
  158. FAST
  159. int t=1;
  160. // cin >> t;
  161. while (t--) sol();
  162. }
  163.  
Success #stdin #stdout 0.01s 5428KB
stdin
Standard input is empty
stdout
Standard output is empty